Confused on whether to express time complexity wit

问题:

How to decide on expressing time complexity of algorithm ?

Should we choose to express time complexity in terms of O(n) or theta(n) ? Because a function f(n) can be expressed as either Big-Oh(g(n)) or theta (g(n)).

When do we choose big-oh over theta ?

回答1:

Use Big Theta notation when you want to also specify a lower bound. f(n) = O(g(n)) says that f is bounded above by g, whereas f(n) = Theta(g(n)) says that f is bounded both above and below by g.

In other words, there are constants k1 and k2 such that k1 * |g(n)| <= |f(n)| <= k2 * |g(n)|