4 ms·
I don't really know why Big-O notation is so common , even though Big O is the upper bound . For me it is more practical and logical to use the Big Θ (Theta) no
by fmax30 13y ago
I don't really know why Big-O notation is so common , even though Big O is the upper bound .
For me it is more practical and logical to use the Big Θ (Theta) notation as it provides a tighter bounder which is more understand able.
Also Big O is very misleading to the new comers, as they are usually confused when they see something like
O(n) = O(n^2)
which is perfectly valid , as the Big O notation is only the upper bound albeit it will be a loose upper bound.
For all we care , we can write the Big O of
for ( i = 0 ; i < n ; i++)
{ cout<<"I am constant time operation"; }
as O( n!) , it won't be mathematically wrong but again it would be very misleading and loose :).
So my advice to everyone is to use the Big Θ notation
As f(x)= Big Θ(g(x)) when f(x) = Big O ( g(x) ) and Big Ω(g(x)) .
Here for those that don't know what Big Ω(g(x)) (read Big omega) is, it is a lower bound . In English that would be that your loop will execute/iterate at least g(x) times.
Now before people get any more confused Big Θ(g(x)) is a tight bound , that means that your code/loop will run at least C1 * (g(x)) and at most C2 * (g(x)) .
where C1 and C2 are two constants .
If anyone is interested they should really read CLRS. It has an excellent chapter on calculating and explaining the time complexities.
- xentronium 13y agoTheta is much harder to type and slightly harder to write. Besides, people are trying to be reasonable about their bounds.
- oskarkv 13y agoOf course O(n) is not equal to O(n^2). O(n) is a set, and O(n^2) is a different set.
- fmax30 13y agoBig O is a upper bound , what I meant was that if a piece of code has O(n) then it also has O(n^2). With emphasis on the upper bound f(x) = O(g(x)) if f(x) <= cg(x). so my point is if f(N) = O(N) then f(N) is also equal to O(N^2) as f(N) <= CN^2 .