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

Table of Contents

Introduction
Repository
Exercise 2-22
- Question
- Solution
  - The solution by normal inequation relations
  - The solution using the result of the previous exercise 2-21

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

Question

Show that for any real constants $a$ and $b$ , $b > 0$

\begin{equation} (n+a)^b=ʘ(n^b) \end{equation}

Solution

There are at least two distinct approaches for this problem.

The solution by normal inequation relations

For large enough $n$ , $n$ satisfies the following inequation:

\begin{equation} n \ge max\{-2a, 2a\} \end{equation}

[1] In that time, $n$ and $a$ satisfies a inequation and both hands of the statement is greater than or equal to 0.

\begin{equation} \frac{n}{2} \le n+a \end{equation}

Raise to the both sides:

\begin{equation} \left(\frac{n}{2}\right)^b \le (n+a)^b \end{equation}

So,

\begin{equation} (n+a)^b=\Omega(n^b) \end{equation}

[2] For large enough n, $n \ge a$ , so,

\begin{equation} (n+a)^b \le (n+n)^b=2^bn^b \end{equation}

So,

\begin{equation} (n+a)^b=O(n^b) \end{equation}

[1] and [2] derives:

\begin{equation} (n+a)^b=ʘ(n^b) \end{equation}

The solution using the result of the previous exercise 2-21

Using binomial expansion to $(n+a)^b$ , we get the following statement:

\begin{equation} (n+a)^b=n^b+\sum_{i=0}^{b-1}a_in^i \end{equation}

The result of exercise 2-21 says the second term of the left-hand side in above equation is $O(n^{b-1})$ .
So,

\begin{align} (n+a)^b&=n^b+\sum_{i=0}^{b-1}a_in^i\\ &=\Theta(n^b)+O(n^{b-1})=\Theta(n^b)\:\text{(the answer)} \end{align}