Chapter 4, Problem 24R

Explanation of Solution

Given:

It is given that the $n$ is $O\left(nlogn\right)$

Big-Oh notation:

In big-Oh notation, let “f” and “g” be functions from the integers or the real numbers to the real numbers. It means that f(x) is “$\text{O}\left(\text{g}\left(\text{x}\right)\right)$”if there are constants “C” and “k” such that

$\left|\text{f}\left(\text{x}\right)\right|\le \text{C}\left|\text{g}\left(\text{x}\right)\right|\text{where}\text{x > k}$

Proof:

According to the big-oh notation, the upper bound can be written as:

$\begin{array}{c}\log (1)+\log 2+\mathrm{}\end{array}$