Answer to Question #267492 in Discrete Mathematics for Raghuveer

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$