Chapter 2, Problem 5E

Explanation of Solution

Asymptotic Notation Big O:

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

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

Example:

Let us assume that,

$\begin{array}{l}{\text{f}}_{\text{1}}\left(\text{n}\right){\text{ = an}}^{\text{2}}\text{+ O}\left(\text{n}\right)\text{=O}\left({\text{n}}^{\text{2}}\right)\\ {\text{f}}_{\text{2}}\left(\text{n}\right)\text{ = cn+d=O}\left(\text{n}\right)\\ \text{g}\left(\text{n}\right){\text{ = n}}^{}\end{array}$