Published on

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

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-21

Question

Prove that for all k ≥ 0 and all sets of real constants {ak,ak−1,...,a1,a0}\{a_k, a_k−1,...,a_1, a_0\},

aknk+ak−1nk−1+....+a1n+a0=O(nk)a_kn^k + a_{k−1}n^k−1 + .... + a_1n + a_0 = O(n^k)

Solution

There are two distinct approaches for this problem.

The solution using formula of the sum of geometric seris

[1] The case n=1n=1:

LHS=Constant.RHS=O(1)\begin{align} LHS&=Constant.\\ RHS&=O(1) \end{align}

So the statement holds.

[2] The case n≥2n\ge2:

LHS=aknk+∑i=0k−1aini\begin{equation} LHS=a_kn^k+\sum_{i=0}^{k-1}a_in^i \end{equation}

Set bb as:

b=max⁡{ai:i∈Z∧0≤i≤k−1}\begin{equation} b=\max \{ a_i : i \in \mathbb{Z} \land 0 \leq i \leq k-1 \} \end{equation}

Amount b derives a new binding below:

∑i=0k−1aini≤b∑i=0k−1ni\begin{equation} \sum_{i=0}^{k-1}a_in^i\le b\sum_{i=0}^{k-1}n^i \end{equation}

We can apply the formula of the sum of geometric seris to this.

b∑i=0k−1ni=b(nk−1)n−1\begin{equation} b\sum_{i=0}^{k-1}n^i=\frac{b(n^k-1)}{n-1} \end{equation}

Since n≥2n\ge2,

b(nk−1)n−1≤b(nk−1)\begin{equation} \frac{b(n^k-1)}{n-1}\le b(n^k-1) \end{equation}

So,

b∑i=0k−1ni=O(nk)\begin{equation} b\sum_{i=0}^{k-1}n^i=O(n^k) \end{equation}

Equation (3), (5) and (8) derive:

aknk+ak−1nk−1+....+a1n+a0=O(nk)\begin{equation} a_kn^k + a_{k−1}n^k−1 + .... + a_1n + a_0 = O(n^k) \end{equation}

Using [1] and [2], the statement holds.

The solution using induction

Set func(m)func(m) as:

func(m)=∑i=0mak−ink−i{0≤m≤k}\begin{equation} func(m)=\sum_{i=0}^{m}a_{k-i}n^{k-i}\qquad\{ 0 \leq m \leq k \} \end{equation}

We'll prove func(m)=O(nk)func(m)=O(n^k) for all mm.

[1] the case m=0m=0

func(0)=aknk=O(k)\begin{equation} func(0)=a_kn^k=O(k) \end{equation}

[2] induction for m′m' and m′+1m'+1

Assume func(m′)=O(nk)func(m')=O(n^k) when m=m′m=m'.

Think of func(m′+1)func(m'+1).

func(m′+1)=func(m′)+ak−m′−1nk−m′−1\begin{equation} func(m'+1)=func(m')+a_{k-m'-1}n^{k-m'-1} \end{equation}

The definition of OO derives:

func(m′)≤c1nk  for  n≥n1\begin{equation} func(m')\le c_1n^k \:\: \text{for}\:\: n\ge n_1 \end{equation}

And since nn is large enough number,

nk−m′−1≤nk\begin{equation} n^{k-m'-1}\le n^k \end{equation}

Statement (12)-(14) derives:

func(m′+1)≤(c1+ak−m′−1)nk  for  n≥n1\begin{equation} func(m'+1)\le (c_1+a_{k-m'-1})n^k \:\: \text{for}\:\: n\ge n_1 \end{equation}

So,

func(m′+1)=O(nk)\begin{equation} func(m'+1)=O(n^k) \end{equation}

From [1] and [2], func(m)=O(nk)func(m)=O(n^k) is proved.

The pattern

func(k)=aknk+ak−1nk−1+....+a1n+a0=O(nk)\begin{align} func(k)&=a_kn^k + a_{k−1}n^k−1 + .... + a_1n + a_0\\ &=O(n^k) \end{align}

is what we want to prove.