Question

Suppose T(n) and f(n) and two functions. Write asymptotic notations (Ο, Ω, Θ) using these two functions and explain the growth rate of these functions in each notation.

Answer 1

$f(n)=O(T(n))$ if there exists a positive real number M and a real number n₀ such that

$f(n)\le MT(n)$ for all $n\ge n_0$

$f(n)=\Omega(T(n))$ if there exists a positive real number M and a real number n₀ such that

$f(n)\ge MT(n)$ for all $n\ge n_0$

$f(n)=\theta(T(n))$ if there exists a positive real numbers M₁, M₂ and a real number n₀ such that

$M_1T(n)\le f(n)\le M_2T(n)$ for all $n\ge n_0$