Chapter 4, Problem 20R

Explanation of Solution

Given:

It is given that if $f\left(n\right)$ is $O\left(g\left(n\right)\right)$ if and only if the function $g\left(n\right)$ is $\Omega \left(f\left(n\right)\right)$

Asymptotic notation:

In asymptotic notation for lower bound, let “f” and “g” be functions from the integers or the real numbers to the real numbers. It means that $\Omega \left(g\left(n\right)\right)= f\left(n\right)$ if there exist positive constants “$c$”$\left(c>0\right)$ in real numbers, such that $0\le cg\left(n\right)\le f\left(n\right)$ for all $n\ge n_0$ .

Proof:

Let us assume that $g\left(n\right)$ and $f\left(n\right)$ be functions mapping nonnegative integers to real numbers