Chapter 4, Problem 24R

Explanation of Solution

Big-O:

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.

Given:

If $\text{d}\left(\text{n}\right)\text{ is O}\left(\text{f}\left(\text{n}\right)\right)\text{ and e}\left(\text{n}\right)\text{ is O}\left(\text{g}\left(\text{n}\right)\right)$ then $\text{d}\left(\text{n}\right)-\text{e}\left(\text{n}\right)$ is not necessarily of $\text{ O}\left(\text{f}\left(\text{n}\right)-\text{g}\left(\text{n}\right)\right)$

Proof:

Assume that $\text{d}\left(\text{n}\right)$ is $\text{O}\left(\text{f}\left(\text{n}\right)\right)$, and $\text{e}\left(\text{n}\right)$ is $\text{O}\left(\text{g}\left(\text{n}\right)\right)$