big-Oh help
Hi guys,
I'm reading some notes about big-Oh, but some points really confused me.
First, there is a theorem on the notes that says(lg( n))^x is O( n^y ), for any constans x, y in R. Can anyone please tell me why? and how should the constant y be determined? Is y the power of n in lgn on the LHS in that above formula?
Seond, if we assume that every single line in an algorithm takesO(1) time, and now we have a loop that has three lines and is iterated m times, can we say this loop takesm*O(1) time?If so, why?
Any help appreciated, thanks.
[599 byte] By [
sdpa] at [2007-10-2 18:07:00]
I don't reply here except once every year or two, so I'll be brief.
>(lg( n))^x is O( n^y )
is a confusing statement to me with respect to "big Oh" notation, or worst-case complexity...Constants are usually ignored, we normally care about how the function behaves as the size of the input, n, grows.
In general, to say that some function "f(n)" is in O("g(n)") means that as n grows from 0 to infinity, that f(n) performs no worse than g(n), so there are many functions that fall in this class.
So, for your example, if you have a single loop with 3 lines, then it is O(n), where n is the number of times the loop iterates.
See the following for details on algorithm analysis:
http://hetland.org/algorithms/complexity.php
http://www.sfs.uni-tuebingen.de/~nvail/SS05/analysis/analysis.html
regards,
Tom Myers
The statement: lg(n)^x is O(n^y) for all x and for all y, needs to be understood in the context that big Oh is an upper bound. Not a tight upper bound and not a simultaneous upper and lower bound.
The function n is O(n^2). (According to Cormen, Lieserman, and Rivest - introduction to Algorithms)
You don't see that written often because O(n) is a tighter bound for n than is O(n^2).
What is means is that lg(n)^ x no matter how big x is, is bounded by n^y no matter how small y is.
Here is the problem.
What Big Oh for lg(n) + some constant?
Easy, it is just O(lg n) because you can through out additive constants.
What is Big Oh for k*lg(n)
Also easy, it is bounded above by lg(n) because by definition you can find a constant C such that k*lg(n) is bounded by C*lg(n) so you can throw out multiplicative constants as well.
But what is Big Oh for lg(n)^k.
Hmm... it isn't log(n). It grows faster than just a multiplicative constant times a log function. Is it polynomial or something like say squareRoot(n), no it grows slower than that. It grows slower than any polynomial.
So what is the name of the function that grows slower than any polynomial but grows faster than any log? Well it doesn't have a name.
The expression above helps you nail down some chunk where you find yourself saying, "well we binary search this thing which is lg(n) stages and at each stage I have to search for this other thing which is also lg(n) so I got a lg(n)squared portion in my algorithm. How slow is that? and the answer is worse than log but not as bad as polynomial.
