Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E2-17'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 2-17

Question

For each of the following pairs of functions f(n) and g(n), give an appropriate positive constant cc such that f(n)≤c⋅g(n)f(n) ≤ c · g(n) for all n>1n > 1.

(a)  f(n)=n2+n+1,g(n)=2n3f(n) = n^2 + n + 1, g(n)=2n^3
(b)  f(n)=n√n+n2,g(n)=n2f(n) = n√n + n^2, g(n) = n^2
(c)  f(n)=n2−n+1,g(n)=n2/2f(n) = n^2 − n + 1, g(n) = n^2/2

Solution

Question(a)

Combine and consider a new function:

h(n)=f(n)cg(n)=1(2cn)(1+1n+1n2)\begin{align} h(n)&=\frac{f(n)}{cg(n)}\\ &=\frac{1}{(2cn)}(1+\frac{1}{n}+\frac{1}{n^2}) \end{align}

Function h(n)h(n) decreases monotonically with n. So If the inequation h(n)≤1h(n)\le1 holds when n=1n=1, it holds for all nn.

Solve the equation below and we get the result c value.

h(1)=1  ⟺  c=32(the answer)\begin{align} h(1)&=1\\ \iff c&=\frac{3}{2} \qquad(\text{the answer}) \end{align}

Question(b)

Combine and consider a new function:

h(n)=f(n)cg(n)=1c(1+1n)\begin{align} h(n)&=\frac{f(n)}{cg(n)}\\ &=\frac{1}{c}(1+\frac{1}{\sqrt{n}}) \end{align}

By the same discussion used in question(a) (Monotonically decreasing trend), c is determined as below:

h(1)=1  ⟺  c=2(the answer)\begin{align} h(1)&=1\\ \iff c&=2\qquad(\text{the answer}) \end{align}

Question(c)

Combine and consider a new function:

h(n)=f(n)cg(n)=2(n2−n+1)cn2\begin{align} h(n)&=\frac{f(n)}{cg(n)}\\ &=\frac{2(n^2-n+1)}{cn^2} \end{align}

The numerator has the maximum when n=1n=1 and the denominator has the minimum at the same time.
So If the inequation h(n)≤1h(n)\le1 holds when n=1n=1, it holds for all nn.

h(1)=1  ⟺  c=2(the answer)\begin{align} h(1)&=1\\ \iff c&=2\qquad(\text{the answer}) \end{align}