Chapter 4, Problem 1P

(a)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=2T\left(n/2\right)+n^4$ .

Explanation:

For a divide and conquer recurrence of the form $T\left(n\right)=aT\left(n/b\right)+f\left(n\right)$ where $a\ge 1,b>1$ and $f\left(n\right)>0$, the following three cases can happen:

Case 1: If $f\left(n\right)=O\left(n^{{\log }_{b}a-\epsilon }\right)$ for some constant $\epsilon >0$ then $T\left(n\right)=\Theta \left(n^{{\lg }_{b}a}\right)$ .

Case 2: If $f\left(n\right)=\Theta \left(n^{{\lg }_{b}a}\right)$ then $T\left(n\right)=\Theta \left(n^{{\lg }_{b}a}\log n\right)$ .

Case 3: If $f\left(n\right)=\Omega \left(n^{{\log }_{b}a+\epsilon }\right)$ for some constant $\epsilon >0$ and if $af\left(n/b\right)\le cf\left(n\right)$ for some constants $c>1$ and sufficiently large $n$ then $T\left(n\right)=\Theta \left(f\left(n\right)\right)$ .

The values of $a,b$ and $f\left(n\right)$ are 2, 2 and $n^4$ respectively.

Therefore, $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n$ and $f\left(n\right)=1$ . Here, $f\left(n\right)=\Omega \left(n^{{\log }_{2}2+\epsilon }\right)$ where $\epsilon =3$ .

So, case 3 of the master method applies.

Hence, $T\left(n\right)=\Theta \left(f\left(n\right)\right)=\Theta \left(n^4\right)$ .

(b)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=T\left(7n/10\right)+n$ .

Explanation:

The values of $a,b$ and $f\left(n\right)$ are 1, $10/7$ and $n$ respectively.

Therefore, $n^{{\log }_{b}a}=n^{{\log }_{10/7}1}=n^0=1$ and $f\left(n\right)=n$ . Here, $f\left(n\right)=\Omega \left(n^{{\log }_{4}2+\epsilon }\right)$ where $\epsilon =1/2$ .

So, case 3 of the master method applies.

Hence, $T\left(n\right)=\Theta \left(f\left(n\right)\right)=\Theta \left(n\right)$ .

(c)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=16T\left(n/4\right)+n^2$ .

Explanation:

The values of $a,b$ and $f\left(n\right)$ are 16, 4 and $n^2$ respectively.

Therefore, $n^{{\log }_{b}a}=n^{{\log }_{4}16}=n^2$ and $f\left(n\right)=\Theta \left(n^{{\log }_{b}a}\right)=\Theta \left(n^2\right)$ .

So, case 2 of the master method applies.

Hence, $T\left(n\right)=\Theta \left(n^c\lg n\right)=\Theta \left(n^2\lg n\right)$ .

(d)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=7T\left(n/3\right)+n^2$ .

Explanation:

The values of $a,b$ and $f\left(n\right)$ are 7, 3 and $n^2$ respectively.

Therefore, $n^{{\log }_{b}a}=n^{{\log }_{3}7}$ and $f\left(n\right)=n^2$ . Here, $f\left(n\right)=\Omega \left(n^{{\log }_{4}2+\epsilon }\right)$ where $\epsilon =3/2$ .

So, case 3 of the master method applies.

Hence, $T\left(n\right)=\Theta \left(f\left(n\right)\right)=\Theta \left(n^2\right)$ .

(e)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=7T\left(n/2\right)+n^2$ .

Explanation:

The values of $a,b$ and $f\left(n\right)$ are 7, 2 and $n^2$ respectively.

Therefore, $n^{{\log }_{b}a}=n^{{\log }_{2}7}$ and $f\left(n\right)=n^2$ . Here, $f\left(n\right)=O\left(n^{{\log }_{2}7-\epsilon }\right)$ where $\epsilon >0$ .

So, case 1 of the master method applies.

Hence, $T\left(n\right)=\Theta \left(n^{{\log }_{b}a}\right)=\Theta \left(n^{{\log }_{2}7}\right)$ .

(f)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=2T\left(n/4\right)+\sqrt{n}$ .

Explanation:

The values of $a,b$ and $f\left(n\right)$ are 2, 4 and $\sqrt{n}$ respectively.

Therefore, $n^{{\log }_{b}a}=n^{{\log }_{4}2}=\sqrt{n}$ and $f\left(n\right)=\Theta \left(n^{{\log }_{b}a}\right)=\Theta \left(\sqrt{n}\right)$ .

So, case 2 of the master method applies.

Hence, $T\left(n\right)=\theta \left(n^{{\lg }_{4}2}\lg n\right)=\theta \left(\sqrt{n}\lg n\right)$ .

(g)

Program Plan Intro

To determine the asymptotic bounds for the recurrence relation using master method.

Explanation of Solution

Given Information: The recurrence relation is $T\left(n\right)=T\left(n-2\right)+n^2$ .

Explanation:

The recurrence relation is not in the form of master theorem. Therefore, it cannot be solve by master theorem.

Solve the recurrence relation $T\left(n\right)=T\left(n-2\right)+n^2$

as follows:

  $\begin{array}{c}T\left(n\right)=T\left(n-2\right)+n^2\\ =n^2+{\left(n-2\right)}^2+T\left(n-4\right)\\ =n^2{\displaystyle \sum _{i=0}^{n/2}1}+4{\displaystyle \sum _{i=0}^{n/2}{i}^2}-4n{\displaystyle \sum _{i=0}^{n/2}i}\\ =n^2\cdot \frac{n}{2}+4\cdot \frac{1}{3}\left(2n^3+6n^2+4n\right)+4n\cdot \frac{1}{2}\left(n^3+2n^2\right)\\ =\frac{2n^3}{3}+n^2+\frac{4}{3}n\\ =\Theta \left(n^3\right)\end{array}$

Therefore, the asymptotic notation of the recurrence $T\left(n\right)=T\left(n-2\right)+n^2$ is $\Theta \left(n^3\right)$ .