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.
Big 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 .
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.