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 )
}
}
}Asymptotic running times - revision question, not homework
Author
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
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"
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]
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]
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.
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.
Quote:Original post by egwenejsQuote: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.
Quote:Original post by alvaro1) 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).
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...
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
