In code complexity measure,
Big Omega gives us asymptotic lower bound function g(n).
Big Theta gives us asymptotically tight bound function g(n), i.e. both lower and upper bound being c1.g(n) and c2.g(n) respectively.
Big Omicron gives us asymptotic upper bound function g(n).
Most of the time we talk about Big Oh. That is actually Big Omicron.
[The character O is the upper-case Greek letter Omicron, not English letter O]
And surprisingly, when we say, complexity of a code is O(N^2) etc,
we really mean Big Theta! We not only mean, N^2 being the upper bound,
but also we mean, N^2 is the lower bound too. Isn't it?
1 comment:
Yes, exactly. We should use big theta whenever possible as it conveys more information. When describing code or algorithm complexity (whether worst-case, best case, or average case) our analysis is usually complete enough that we can state a big-theta result.
Big oh (or omicron) and big theta are most useful for stating upper and lower bounds on problem complexity. Analysis of problem complexity is much more difficult and most techniques only give you an upper bound or a lower bound. Even when the upper and lower bound are known to be the same, they are usually obtained separately.
Nevertheless, most people say "big oh" even if the meaning they intend to convey is that of "big theta".
I think this is because most people --or rather most people in the small subset who wish to convey something about algorithm complexity-- fit into one of two kinds: The first kind don't know what big theta means, so they say "big oh". The second kind know the difference, but say "big oh" just in case they are talking to a person of the first kind.
Post a Comment