Asymptotic Notations - Big Theta

Big-Theta is the tight bound or average bound of a function is denoted as notation (Θ).

Definition: Suppose we have two functions f(n) and g(n), then the function f(n) = Θ(g(n) if and only if there exists three positive constants c1, c2, and k, such that c1 * g(n) <= f(n) <= c2 * g(n) for all n >= k.

For example:

Suppose, if f(n) = 2 * n + 3, then

1 * n <= 2 * n + 3 <= 5 * n for all n >= 1.

In the above equation,
c1 = 1, c2 = 5, k = 1, and g(n) = n

Now we know that, 1< log(n) < n^(1/2) < n < n log(n) < n^2 < n^3 < — < 2^n < 3^n <---- n^n.
In the above comparison, n is the tight bound.

This symbolizes,

  1. f(n) = Θ(n) — True
  2. f(n) = Θ(n^2) — False
  3. f(n) = Θ(1) — False, and so on…

**That is, in Big-Theta, we have only one g(n), which in this case is Θ(n).

1 Like