• Advertisement
Sign in to follow this  

Asymptotic running times - revision question, not homework

This topic is 3323 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

First off this is a revision question for an exam I have tomorrow, this is NOT homework to be handed in, but I understand if it goes under the same rules! Got a revision question I need help with for an exam tomorrow, it's late so I can't quite figure it out :S Q. b. Consider the following piece of code
for (int i=0 ; i<n ; i++) 
{ 
   for (int j=0 ; j<n ; j++) 
   { 
      for (int k=0 ; k<=i ; k++) 
      { 
         print (i + j + k ) 
      } 
   } 
}
1) Find an expression in terms of n for the number of times the function print is invoked. 2) Express the asymptotic running time using the big­O notation. The tricky part is the third loop, which is dependant on i, so it's not called n3 times. So the innermost loop runs once, then twice, then 3 times ... then n times. Hmm...

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Rajveer
The tricky part is the third loop, which is dependant on i, so it's not called n3 times. So the innermost loop runs once, then twice, then 3 times ... then n times. Hmm...


"What is the sum of first n natural numbers"

Share this post


Link to post
Share on other sites
1) n^2*(n+1)/2
2) O(n^2*(n+1)/2) // although there are other ways of expressing this: The question wasn't posed very well...

[Edited by - alvaro on January 12, 2009 10:21:41 PM]

Share this post


Link to post
Share on other sites
Well, since you gave it away, it's n(n+1)/2 in fact, and therefore the algorithmic complexity is equivalent to O(n^2) as n tends to +inf.

Share this post


Link to post
Share on other sites
Quote:
Original post by janta
Well, since you gave it away, it's n(n+1)/2 in fact, and therefore the algorithmic complexity is equivalent to O(n^2) as n tends to +inf.


No, it isn't. What you have only counts the i and k loops, so you need to add in the j loop too.

Share this post


Link to post
Share on other sites
Quote:
Original post by egwenejs
Quote:
Original post by janta
Well, since you gave it away, it's n(n+1)/2 in fact, and therefore the algorithmic complexity is equivalent to O(n^2) as n tends to +inf.


No, it isn't. What you have only counts the i and k loops, so you need to add in the j loop too.

My bad, I just wrote based on Antheus's reply (which appears to be a hint at the solution and not the solution itself - I should have known better) and didn't properly look at the original problem. I mean the sum of N first natural numbers is n(n+1)/2

Indeed the correct reply to the original problem is O(n^3), I stand corrected.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
1) n^2*(n+1)/2
2) O(n^2*(n+1)/2) // although there are other ways of expressing this: The question wasn't posed very well...
1) is pretty much spot on. Big-O notation though doesn't carry any component of the equation that isn't highest order. So really, n^2 * (n + 1) / 2 == O(n^3), which is more in-line with what big-O notation is all about. O(n^2*(n+1)/2) will in all likelihood get him chopped up by his teachers, or at least it would have gotten me chopped up by mine if I had turned that answer in, even though it is technically correct in that it isn't technically incorrect. It is wastefully detailed, as it is perfectly sufficient and completely equal within this notation to just say O(n^3).

Share this post


Link to post
Share on other sites
Thanks for the replies guys, don't worry you didn't give the whole answer away to me without making me think!

I worked out the first part from Antheus's first post but was still having trouble with the second. I then thought that the big O notation would have been O(n^2*(n+1)/2) too but thanks for clearing up why it may be technically correct but should be n^3.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement