Answer to Question #265244 in Discrete Mathematics for Isha

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$