Big Omega, Big Theta and Big Omicron.

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?

No comments: