• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Liutauras Vilda
  • Bear Bibeault
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Paul Clapham
  • Devaka Cooray
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Frits Walraven
Bartenders:
  • Carey Brown
  • salvin francis
  • Claude Moore

Run-time analysis of pseudo Code  RSS feed

 
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 64172
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please explain what you are trying to find.
 
Saloon Keeper
Posts: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's a function that has the exact same results as your pseudo-code, except it performs in O(1).
 
Hans Peterson
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 64172
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 10136
214
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Master Rancher
Posts: 3189
119
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for youre help folks. It's clear now
 
There's a way to do it better - find it. -Edison. A better tiny ad:
Create Edit Print & Convert PDF Using Free API with Java
https://coderanch.com/wiki/703735/Create-Convert-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!