Chapter 4, Problem 31R

Explanation of Solution

Big-O notation:

A function $g\left(n\right)$ is $O\left(f\left(n\right)\right)$ if there exists a constant $c>0$ such that “$\text{cf}\left(\text{n}\right)$ grows faster than $g\left(n\right)$ for all $n>=n_0$ , that is, $g\left(n\right)$ is $O\left(f\left(n\right)\right)$ iff for some constants “c” and “$n_0$”, $g(n)<=cf(n)$ for all $n>=n_0$. Here, $\text{f}\left(\text{n}\right)$ denotes upper bound for $g\left(n\right)$. The important points for above statements are as follows:

• “n” is the data set size.
• $\text{f}\left(\text{n}\right)$ denotes a function that is calculated while taking n as the parameter.
• $O\left(f\left(n\right)\right)$ means that curve denoted by $\text{f}\left(\text{n}\right)$ is an upper bound for a function’s need for resources.

To prove:

$n$ is $O\left(nlogn\right)$

Proof:

Consider that the given condition is true