Asymptotic Notations - Big Theta

Software Development
#1

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
#2
#3

Actually big-theta notation gives you a tight bound. It also tells that the given algorithm satisfy both big-O and big-Omega.

say, f(n) and g(n) are positive valued function that take positive value ‘n’ as argument then big-theta can be defined as

Theta(g(n)) = { f(n) : there exists positive constants c1,c2 and n1 such that 0<=c1.(g(n))<= f(n)<=c2.(g(n)) for all n>=n1 }

that means f(n) can be sandwiched between c1.g(n) and c2.g(n).

#4