Chapter 9.6, Problem 9.15CP

Explanation of Solution

Complexity of an algorithm:

The complexity of an algorithm solves a computations problem by finding the number of basic steps required for an input.

To show every function in $O\left(g\left(n\right)+100\right)$ is also in $O\left(g\left(n\right)\right)$:

$\begin{array}{l}\text{Let us consider }g\left(n\right)\ge 1\text{ for all }n\ge 1\\ \text{Clearly }100\le 100g\left(n\right)\text{ for all }n\ge 1\text{ this gives that }\\ g\left(n\right)+100\le g\left(n\right)+100g\left(n\right)\\ g\left(n\right)+100\le 101g\left(n\right)\text{ for all }n\ge 1\\ \text{If }f\left(n\right)\text{ is in }O\left(g\left(n\right)+100\right),\text{ there exists a positive }K\text{ such that }\end{array}$

$\begin{array}{l}f\left(n\right)\le K\left(g\left(n\right)+100\right)\\ f\left(n\right)\le K(\end{array}$