Theta and Big O notation in simple language
While trying to understand the difference between Theta and O notation I came across the following statement :
The Theta-notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
But I do not understand this. The book explains it mathematically, but it's too complex and gets really boring to read when I am really not understanding.
Can anyone explain the difference between the two using simple, yet powerful examples.
Big O is giving only upper asymptotic bound, while big Theta is also giving a lower bound.
Everything that is Theta(f(n)) is also O(f(n)) , but not the other way around.
T(n) is said to be Theta(f(n)) , if it is both O(f(n)) and Omega(f(n))
For this reason big-Theta is more informative then big-O notation, so if we can say something is big-Theta, it's usually preferred. However, it is harder to prove something is big Theta, than to prove it is big-O.
For example , merge sort is both O(n*log(n)) and Theta(n*log(n)) , but it is also O(n2), since n2 is asymptotically "bigger" than it. However, it is NOT Theta(n2), Since the algorithm is NOT Omega(n2).
Omega(n) is asymptotic lower bound. If T(n) is Omega(f(n)) , it means that from a certain n0 , there is a constant C1 such that T(n) >= C1 * f(n) . Whereas big-O says there is a constant C2 such that T(n) <= C2 * f(n)) .
All three (Omega, O, Theta) give only asymptotic information ("for large input"):
Note that this notation is not related to the best, worst and average cases analysis of algorithms. Each one of these can be applied to each analysis.
I will just quote from Knuth's TAOCP Volume 1 - page 110 (I have the Indian edition). I recommend reading pages 107-110 ( section 1.2.11 Asymptotic representations )
People often confuse O-notation by assuming that it gives an exact order of Growth; they use it as if it specifies a lower bound as well as an upper bound. For example, an algorithm might be called inefficient because its running time is O(n^2). But a running time of O(n^2) does not necessarily mean that running time is not also O(n)
On page 107,
1^2 + 2^2 + 3^2 + ... + n^2 = O(n^4) and
1^2 + 2^2 + 3^2 + ... + n^2 = O(n^3) and
1^2 + 2^2 + 3^2 + ... + n^2 = (1/3) n^3 + O(n^2)
Big-Oh is for approximations. It allows you to replace ~ with an equals = sign. In the example above, for very large n, we can be sure that the quantity will stay below n^4 and n^3 and (1/3)n^3 + n^2 [and not simply n^2]
Big Omega is for lower bounds - An algorithm with Omega(n^2) will not be as efficient as one with O(N logN) for large N. However, we do not know at what values of N (in that sense we know approximately)
Big Theta is for exact order of Growth, both lower and upper bound.
Here's my attempt:
A function, f(n) is O(n) , if and only if there exists a constant, c , such that f(n) <= c*g(n) .
Using this definition, could we say that the function f(2^(n+1)) is O(2^n) ?
In other words, does a constant 'c' exist such that 2^(n+1) <= c*(2^n) ? Note the second function ( 2^n ) is the function after the Big O in the above problem. This confused me at first.
So, then use your basic algebra skills to simplify that equation. 2^(n+1) breaks down to 2 * 2^n . Doing so, we're left with:
2 * 2^n <= c(2^n)
Now its easy, the equation holds for any value of c where c >= 2 . So, yes, we can say that f(2^(n+1)) is O(2^n) .
Big Omega works the same way, except it evaluates f(n) >= c*g(n) for some constant 'c' .
So, simplifying the above functions the same way, we're left with (note the >= now):
2 * 2^n >= c(2^n)
So, the equation works for the range 0 <= c <= 2 . So, we can say that f(2^(n+1)) is Big Omega of (2^n) .
Now, since BOTH of those hold, we can say the function is Big Theta ( 2^n ). If one of them wouldn't work for a constant of 'c' , then its not Big Theta.
The above example was taken from the Algorithm Design Manual by Skiena, which is a fantastic book.
Hope that helps. This really is a hard concept to simplify. Don't get hung up so much on what 'c' is, just break it down into simpler terms and use your basic algebra skills.
上一篇: 哦vs大