Chapter 4, Problem 25R

Explanation of Solution

Given:

It is given that the $n^2$ is $\Omega \left(nlogn\right)$

Big-Omega 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 $f\left(n\right)=n^2$ and $g\left(n\right)=nlogn$

• According to big-omega definition, $f\left(n\right)\in \Omega g\left(n\right)$ when 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$.
• In other words, it can written as follows:

  $\begin{array}{l}{n}^2=c\end{array}$