Hey, I hope I put this in the right section. I have a basic question about big o notation. How do you discover if something is O(logn) vs O((logn)^2)? It seems like the graphs are similar, but (logn)^2 has a slightly faster growth rate. I don't know how you would be able to tell for sure. I plug in values for n ( the number of times for a program to run), and then graph the time it takes, and it looks like (logn)^2.
Also, I have read how to calculate big O for for loops, nested for loops, etc. but I have not seen anything for what to do if the for loop does not increment by 1 each time. What if you increase the amount to increment by for 1 each time? So first is n+1, then n+2, n+3,...etc. Graphing that is what looked like (logn)^2 to me, but I'm not sure how to tell for sure.
Sorry if that is confusing,
Thanks
Question about big O algorithm analysis
Page 1 of 18 Replies  4815 Views  Last Post: 21 February 2009  01:13 PM
Replies To: Question about big O algorithm analysis
#2
Re: Question about big O algorithm analysis
Posted 01 February 2009  05:51 AM
A bit confusing but basically, you calculate big O by analysis. Most logarithmiccomplexity functions use recursion so what you do is you write down the recursion equation and solve it.
You can't really solve it by looking at runtimes because any function that takes c * log(n) time to perform (where c is any constant) is O(log n).
If you have the graph then possible you can derive the answer.
You can't really solve it by looking at runtimes because any function that takes c * log(n) time to perform (where c is any constant) is O(log n).
If you have the graph then possible you can derive the answer.
#3
Re: Question about big O algorithm analysis
Posted 01 February 2009  10:32 AM
You can also do it through calculus. If I recall correctly, you take the limit and divide and depending on the answer, the original equation is big order ("O") or little order ("o" of the equation used to check,
#4
Re: Question about big O algorithm analysis
Posted 17 February 2009  12:25 PM
I'm a high school student in preAP CS, so my answer may be a little cruder than the other 2. What I do is increase the size of the problem and record the nubmer of steps for each increment. I then graphed these points and used the function which represented the curve followed. For example, if 1/2 of a parabola was formed, the function was O(n^2). Even if it wasn't an exact graph of n^2, it followed the same pattern.
#5
Re: Question about big O algorithm analysis
Posted 18 February 2009  03:33 AM
How do you identify a complexity function that is something like 'n^3 * log n' or 'n * (log n)^2'?
This post has been edited by Gloin: 18 February 2009  03:34 AM
#6
Re: Question about big O algorithm analysis
Posted 18 February 2009  07:46 AM
A cubic function makes a distinguishing graph. Not sure on the n log n one though.
#7
Re: Question about big O algorithm analysis
Posted 19 February 2009  04:56 AM
KYA, on 18 Feb, 2009  02:46 PM, said:
A cubic function makes a distinguishing graph. Not sure on the n log n one though.
Sure, but the n^3 * log n as from my example is not so easily differentiated from the n^2 * log n. Like you say, as long as you're close to some distinct graph you'll probably do ok but as soon as you have to deal with some more complex function you're in for some problems.
Compare these 2 graphs in for example range [10, 10] and you'll see that they look quite similar.
n * log(n^2)
and
0.01 * n^3
Naturally the later will outgrow the first rather quickly although that is not indicated by the graph. They look very similar and one can easily be mistaken for the other.
#8
Re: Question about big O algorithm analysis
Posted 19 February 2009  07:27 AM
My apologies, I didn't see the '*' between n^3 and log n. That would be terrible to do by hand.
#9
Re: Question about big O algorithm analysis
Posted 21 February 2009  01:13 PM
Graphing running times for asymptotic analysis is bad advice... don't do it. Never graph a program to determine its time complexity, ever.
Page 1 of 1
