#165913 - Rajveer - Mon Jan 12, 2009 10:55 pm
Sorry, this should be moved to off-topic, didn't realise this is gba coding only!
Hope someone can help! 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
| 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...
#165915 - DekuTree64 - Tue Jan 13, 2009 12:11 am
Hmm, according to my graph, the exact number of prints is n2*(1 + (n - 1)/2). I don't know the exact rules of big O notation, but it's still kind of n3-ish.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#165918 - Rajveer - Tue Jan 13, 2009 1:03 am
Thanks for the help, but we both figured out the first part at the same time :D
I've figured out that the number of prints is the sum of natural numbers up to n, times by the number of times we go through the j loop (I think). Which is cool because we both got "( n(n + 1) )/2 * n" !
Now I'm still not sure about the big O notation of the algorithm...
#165919 - Dwedit - Tue Jan 13, 2009 1:30 am
O(N^3)
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#165920 - Rajveer - Tue Jan 13, 2009 1:48 am
But it won't ever be O(N^3) unless the last loop were going from 0 -> n too, no?
On a side note, how in the world did I make 325 posts?!
#165923 - kusma - Tue Jan 13, 2009 2:38 am
It's O(n^3). The big-oh notation describes scaling, not anything else. That is, the scale of n is irrelevant to the big-oh notation (int the same way as O(2n) == O(n)).
Anyway, let's look at some proof of the scaling:
| Quote: |
n=10
n*n*n=1000
n=20
n*n*n=8000
n=40
n*n*n=64000
|
Each time we double n, we the result is multiplied by 8.
Let's try the same thing with your equation (n*n*(1 + (n - 1) / 2)):
| Quote: |
a=10
n*n*(1 + (n - 1) / 2) = 500
a=20
n*n*(1 + (n - 1) / 2) = 4000
a=40
n*n*(1 + (n - 1) / 2) = 32000
|
Yep. Same scaling.
#165928 - Rajveer - Tue Jan 13, 2009 8:50 am
Oh right obviously, thanks for the explanation and help guys!
Off to kick this exams ass!
#165938 - Miked0801 - Tue Jan 13, 2009 7:55 pm
What O(x) means in the real world.
O(1) - Sweet, this goes fast.
O(N) - Sweet, this goes fast.
O(N Log N) - This kinda slows down when we sort 1000 items, but it's still fast.
O(N^2) - Damn this is slow when you get more than 20 guys on screen. What! You used a bubble sort for our actor system?
O(N^3) - If N ever goes above 10, You're fired.
O(N!) - What the hell are you doing implementing a bogo sort on company time?
:)