Chapter 4, Problem 33R

Explanation of Solution

Running time of algorithm:

It is given that Al and bob claims and argues about their algorithms. Al means that the $O\left(nlogn\right)$ is faster than the bob’s algorithm time complexity $O\left(n^2\right)$.

To prove the results, a set of operation is performed to check the result. If the input value of size “n” is less than 100 then the bob’s algorithm $O\left(n^2\right)$ runs faster whereas the value n greater than or equal to 100 the Al ‘s algorithm $O\left(nlogn\right)$ runs faster.

Possibility of $O\left(nlogn\right)$ faster than$O\left(n^2\right)$:

”Yes”, $O\left(nlogn\right)$ faster than $O\left(n^2\right)$, because the linear algo