Search code examples
algorithmasymptotic-complexity

Big Theta Notation formula is confusing need clarity

If the mathematical rule for Big Theta notation is :

f(n) = Theta (g(n)) if and only if f(n) >= cg(n) for some c after n >= n0 >=0

then when f(n) = 5n2 then we consider it as Theta(n2)
Considering 5n2 >= n2 for c = 1 and n0 = 0
But
Why not f(n) = theta(n)
Considering 5n2 >= n for c = 1 and n0 = 0 ??

Solution

  • First of all, Theta(g) is a set of functions. So technically you need to write f in Theta(g) and not f = Theta(g).

    Informally Theta(g) contains all functions that grow equally strong (asymptotically). So it is like an asymptotical = (equal).

    Some f is in Theta(g) iff it is in O(g) and Omega(g) at once.

    Now to your example. We have f(n) = 5n^2. As you said, it is in Theta(n^2) But it is not in Theta(n). Your example was c = 1 and n_0 = 0.

    At this point your formula is wrong. The definition of Big-O is

    enter image description here

    So with a <= and not with >=, that would be Big-Omega.

    We get

    5n^2 <= 1 * n

    for your values, let's plot it for all n >= n_0 = 0:

    enter image description here

    As seen, f is not less than 1 * g for all n >= n_0. Thus, it is not in O(n).

    And since Theta means both, O and Omega, you can't be in Theta if you are not in O.