Win a copy of JDBC Workbook this week in the JDBC and Relational Databases forum
or A Day in Code in the A Day in Code forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Jeanne Boyarsky
• Junilu Lacar
• Henry Wong
Sheriffs:
• Ron McLeod
• Devaka Cooray
• Tim Cooke
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Frits Walraven
• Tim Holloway
• Carey Brown
Bartenders:
• Piet Souris
• salvin francis
• fred rosenberger

# Run-time analysis of pseudo Code

Greenhorn
Posts: 16
• • • • I'm not sure in which Forum to post this question so I put it in Java in General. Please tell me if you know a better fit for this question because I have the feeling I will post some of these in the following days ;)
I'm looking for the return value as a functoin of n in big theta notation for the following pseudo code:

The first (repeat) loop goes (in principle) n/log_2(n) times only that the rest in the division doesn't matter. So I'm looking here for a mathematical way to display only positiv integer. Maybe with the modulo function?
The for loop runs exactly a times and therefore (imagine the result of the division is a positiv integer) has 2* n/log_2(n) calls.
For z I get the value z = n*(2j+1) because in the first step j=0 and z is n since z= 0 +0 +n = (j+1)*n.
Can somebody confirm my results an help me out with the first loop?

Marshal Posts: 69382
276
• • • • Please explain what you are trying to find. Saloon Keeper Posts: 11995
257
• • • • Hans Peterson wrote:I'm not sure in which Forum to post this question so I put it in Java in General.

Since this is not a Java question, I'll move it to our Computing forum.

The first (repeat) loop goes (in principle) n/log_2(n) times only that the rest in the division doesn't matter.

It doesn't. The repeat loop iterates log₂(n) times, exactly as it says on line 8.

What division are you talking about? Why doesn't the rest matter? What rest?

So I'm looking here for a mathematical way to display only positiv integer. Maybe with the modulo function?

What positive integer? I thought you were looking for the Big Theta time complexity class.

The for loop runs exactly a times and therefore (imagine the result of the division is a positiv integer) has 2* n/log_2(n) calls.

It doesn't. a = 2^log₂(n) = n. Again, what division?

For z I get the value z = n*(2j+1) because in the first step j=0 and z is n since z= 0 +0 +n = (j+1)*n.

Just because that's the answer in the first step doesn't make it the answer at the end of the loop.

The second loop runs n times. Every step you add j + n, where j increments with each step. That means that at the end of the loop,

z = n² + 0 + 1 + ... + n-2 + n-1
= n² + n/2(n-1)
= 1½n² - ½n
.

Now, the first loop runs in Θ(log₂(n)) time and the second loop runs in Θ(n) time. Because the second loop has a larger time complexity class, that one determines the time complexity of the function.

If instead of using loops, you calculate z using the formula, the running time of the function will be in Θ(1).

Hans Peterson
Greenhorn
Posts: 16
• • • • It doesn't. a = 2^log₂(n)

Why is this so? Let n be 7. Then log_2(n) is approximately 2.8. Since the loop only repeats until i>2.8 it has 2 steps.
First step: i = 2, a = 2
Second step: i = 3, a = 4

a will allways be a multiple of 2. Thats why I thought I'm not interested in the decimals when I calculate log_2(n).

Stephan van Hulst
Saloon Keeper Posts: 11995
257
• • • • So I guess in your first post by 'division' you meant 'logarithm' and by 'rest in the division' you meant 'decimal part of the logarithm'.

Hans Peterson wrote:a will allways be a multiple of 2.

You mean: a will always be a power of two.

Thats why I thought I'm not interested in the decimals when I calculate log_2(n).

True, and my analysis was based on whole powers of two. a is the largest power of two that is less than or equal to n. Also, there is an edge case where n=1 -> a=2.

This however is of absolutely no consequence to the time complexity class of the function, which is still in Θ(n), because a is always between n/2 and n.

Stephan van Hulst
Saloon Keeper Posts: 11995
257
• • • • Here's a function that has the exact same results as your pseudo-code, except it performs in O(1).

Hans Peterson
Greenhorn
Posts: 16
• • • • Thank you I think I got the first part now.

the second loop runs in Θ(n)

Why isn't the loop running n^2 times? Still I don't quite understand why it runs n^2 times but I tested it until n = 5 and the result always was n^2 times:
n=1 -> z =0+0+1 = 1
n=2 -> z=1+1+2 = 4
n=3 -> z=4+2+3 = 9
n=4 -> z= 9+3+4 = 16
n=5 -> z=16+4+5 = 25

P.S: Is there a Latex mode or something so I can write down the maths a little bit more structured like you?

Campbell Ritchie
Marshal Posts: 69382
276
• • • • Hans Peterson wrote:. . . Is there a Latex mode or something . . .

No, afraid not. I have never seen a LaTeX mode on any website. Stephan was using the code button. Stephan van Hulst
Saloon Keeper Posts: 11995
257
• • • • Those results aren't correct Hans.

n = 1 -> z =  3
n = 2 -> z =  5
n = 3 -> z =  7
n = 4 -> z = 22
n = 5 -> z = 26

The reason you are getting your results is because you're performing f(n) = f(n-1) + n-1 + n, which is NOT what the second loop does.

Hans Peterson wrote:Why isn't the loop running n^2 times? Still I don't quite understand why it runs n^2 times but I tested it until n = 5 and the result always was n^2 times

You are conflating execution result and execution running time. z is the result of the function call. Θ(n) is a complexity class that describes the running time of the function. So while you are correct in saying that the function itself is in Θ(n²), the runtime of the function is in Θ(n), because the second loop never runs more than n times.

I see now in your original post that you're "looking for the return value as a functoin[sic] of n in big theta notation", so you WERE actually asking for the function itself, and not the running time. Then yes, you're correct in saying that the function is in Θ(n²). This however is extremely confusing because complexity classes are usually used to characterize the running time or memory requirements of a function, not its result.

Bartender Posts: 3954
154
• • • • At first I thought Stephan was wrong, but just before pressing the 'reply' button I realized that I myself was wrong. I read 'a = 2*a' as 'a = 2^a', and then making the second error of interpreting this as 'a = Math.pow(2, a)'. Silly me.

But nevertheless interesting by itself. What is the running time in this case? (and you don't need to express the result in BigO notation).

Hans Peterson
Greenhorn
Posts: 16
• • • • Thanks for youre help folks. It's clear now Their achilles heel is the noogie! Give them noogies tiny ad! Devious Experiments for a Truly Passive Greenhouse! https://www.kickstarter.com/projects/paulwheaton/greenhouse-1
• 