• 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
  • Devaka Cooray
  • Knute Snortum
  • Paul Clapham
  • Tim Cooke
Sheriffs:
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Frits Walraven
Bartenders:
  • Ganesh Patekar
  • Tim Holloway
  • salvin francis

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: 64483
225
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please explain what you are trying to find.
 
Saloon Keeper
Posts: 10209
216
  • 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: 10209
216
  • 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: 10209
216
  • 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: 64483
225
  • 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: 10209
216
  • 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.
 
Saloon Keeper
Posts: 3250
128
  • 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
 
Just the other day, I was thinking ... about this tiny ad:
ScroogeXHTML - small and flexible RTF to HTML converter library
https://coderanch.com/t/710903/ScroogeXHTML-RTF-HTML-XHTML-converter
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!