Question

Section 2.2 describes a method for solving recurrence relations which is based on analyzing the recursion tree and deriving a formula for the work done at each level. Another (closely related) method is to expand out the recurrence a few times, until a pattern emerges. For instance, let’s start with the familiar $\mathit{T}\left(n\right)\mathbf{=}\mathbf{2}\mathit{T}\left(n/2\right)\mathbf{+}\mathit{o}\left(n\right)$. Think of $\mathit{o}\left(n\right)$ as being role="math" localid="1658920245976" $\underline{\mathbf{<}}\mathit{c}\mathit{n}$for some constant , so: $\mathit{T}\left(n\right)\mathbf{}\underline{\mathbf{<}}\mathbf{}\mathbf{2}\mathit{T}\left(n/2\right)\mathbf{+}\mathit{c}\mathit{n}$. By repeatedly applying this rule, we can bound $\mathit{T}\left(n\right)$ in terms of $\mathit{T}\left(n/2\right)$, then $\mathit{T}\left(n/4\right)$, then $\mathit{T}\left(n/8\right)$, and so on, at each step getting closer to the value of $\mathit{T}(.)$ we do know, namely .

$\mathit{T}\left(1\right)\mathbf{=}\mathbf{0}\left(1\right)\mathbf{.}$

$$\begin{gathered} \mathit{T}\left(n\right)\mathbf{}\mathbf{\le }\mathbf{2}\mathit{T}\left(n/2\right)\mathbf{+}\mathit{c}\mathit{n} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{\le }\mathbf{2}\left[2T\left(n/4\right)+cn/2\right]\mathbf{+}\mathit{c}\mathit{n}\mathbf{=}\mathbf{4}\mathit{T}\left(n/4\right)\mathbf{+}\mathbf{2}\mathit{c}\mathit{n} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{\le }\mathbf{4}\left[2T\left(n/8\right)+cn/4\right]\mathbf{+}\mathbf{2}\mathit{c}\mathit{n}\mathbf{=}\mathbf{8}\mathit{T}\left(n/8\right)\mathbf{+}\mathbf{3}\mathit{c}\mathit{n} \\ \mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{\le }\mathbf{8}\left[2T\left(n/16\right)+cn/8\right]\mathbf{+}\mathbf{3}\mathit{c}\mathit{n}\mathbf{=}\mathbf{16}\mathit{T}\left(n/16\right)\mathbf{+}\mathbf{4}\mathit{c}\mathit{n} \end{gathered}$$

.

.

.

A pattern is emerging... the general term is

$\mathit{T}\left(n\right)\mathbf{}\mathbf{\le }\mathbf{2}\mathbf{}\mathit{k}\mathit{T}\left(n/2k\right)\mathbf{+}\mathbf{}\mathit{k}\mathit{c}\mathit{n}$

Plugging in $\mathit{k}\mathbf{}\mathbf{=}\mathit{l}\mathit{o}{\mathit{g}}_{\mathbf{2}}\mathit{n}$, we get $\mathit{T}\left(n\right)\mathbf{}\mathbf{\le }\mathit{n}\mathit{T}\mathbf{}\left(1\right)\mathbf{}\mathbf{+}\mathbf{}\mathit{c}\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}_{\mathbf{2}}\mathit{n}\mathbf{=}\mathbf{0}\left(nlogn\right)$.

(a)Do the same thing for the recurrence $\mathit{T}\left(n\right)\mathbf{}\mathbf{=}\mathbf{3}\mathit{T}\left(n/2\right)\mathbf{+}\mathbf{0}\left(n\right)$. What is the general $\mathit{k}$th term in this case? And what value of should be plugged in to get the answer?(b) Now try the recurrence $\mathit{T}\left(n\right)\mathbf{=}\mathit{T}\left(n-1\right)\mathbf{+}\mathbf{0}\left(1\right)$, a case which is not covered by the master theorem. Can you solve this too?

Short answer

answer is not given by the question.

Step-by-step solution

Solution of part (a)

Finding the general term for the following recurrence:

$T\left(n\right)=3T\left(n/2\right)+O\left(n\right)$

Let $O\left(n\right)\le cn$.

Thus, $T\left(n\right)$ can be present as follows:

$T\left(n\right)=3T\left(n/2\right)+cn$…… (1)

$T\left(n\right)=\left(n/2\right)$in this formula it’s represent as follows:

$T\left(n/2\right)\le 3\left(n/4\right)+\left(cn/2\right)$

$T\left(n/4\right)$can be represented as follows:

$T\left(n/2\right)\le 3\left(n/8\right)+\left(cn/4\right)$

$T\left(n/8\right)$can be represented as follows:

$T\left(n/8\right)\le 3\left(n/16\right)+\left(cn/8\right)$

Sub-equation (2) in equation (1). Hence,$T\left(n\right)$can be rewritten as follows:

role="math" localid="1658982909094" $$\begin{gathered} T\left(n\right)\le 3\left(\left(n/4\right)+\left(cn/2\right)\right)+cn \\ \le 9\left(n/4\right)+3\left(cn/2\right)+cn \\ \le 9\left(n/4\right)+5\left(cn/2\right) \end{gathered}$$

Equation (5) can be written as follows:

$T\left(n\right)\le 3^{2}T\left(n/2^2\right)+\left(2cn\left({\left(3/2\right)}^2-1\right)\right)$

The gives a detailed analysis for the formulation of solution as answer:

$$\begin{gathered} T\left(n\right)\le 3^{2}T\left(n/2^2\right)+\left(2cn\left({\left(3/2\right)}^2-1\right)\right) \\ \le 9T\left(n/4\right)+\left(2cn\left(\left(9/4\right)-1\right)\right) \\ \le 9T\left(n/4\right)+\left(2cn\left(5/4\right)\right) \\ \le 9T\left(n/4\right)+cn\left(5/2\right) \\ \le 9T\left(n/4\right)+5\left(cn/2\right) \end{gathered}$$

Substitute equation in equation.

$$\begin{gathered} T\left(n\right)\le 9\left(3T\left(n/8\right)+\left(cn/4\right)+5\left(cn/2\right)\right) \\ \le 27T\left(n/8\right)+9\left(cn/4\right)+5\left(cn/2\right) \\ \le 27T\left(n/8\right)+19\left(cn/4\right) \end{gathered}$$

Equation can be written as follows:

$T\left(n\right)\le 3^{3}T\left(n/2^3\right)+\left(2cn{\left(3/2\right)}^3-1\right)$

Note:

Explanation for the representation of equation as equation has been represented as follows:

$$\begin{gathered} T\left(n\right)\le 3^{3}T\left(n/2^3\right)+\left(2cn\left({\left(3/2\right)}^3-1\right)\right) \\ \le 27T\left(n/8\right)+\left(2cn\left(\left(27/8\right)-1\right)\right) \\ \le 27T\left(n/8\right)+\left(2cn\left(19/8\right)\right) \\ \le 27T\left(n/8\right)+cn\left(19/4\right) \end{gathered}$$

Substitute equation (4) in equation (7).

$$\begin{gathered} T\left(n\right)\le 27\left(3T\left(n/16\right)+\left(cn/8\right)\right)+19\left(cn/4\right) \\ \le 81T\left(n/16\right)+65\left(cn/8\right) \end{gathered}$$

Equation can be written as follows:

$T\left(n\right)\le 3^{4}T\left(n/2^4\right)+\left(2cn\left({\left(3/2\right)}^4-1\right)\right)$

This following is an explanation for such formulation for equation into equation:

$$\begin{gathered} T\left(N\right)\le 3^{4}T\left(n/2^4\right)+\left(2cn\left({\left(3/2\right)}^4-1\right)\right) \\ \le 81T\left(n/16\right)+\left(2cn\left(\left(81/16\right)-1\right)\right) \\ \le 81T\left(n/16\right)+\left(2cn\left(65/16\right)\right) \\ \le 81T\left(n/16\right)+2cn\left(65/16\right) \\ \le 81T\left(n/16\right)+65\left(cn/8\right) \end{gathered}$$

Commonly, it will be written as follow:

$T\left(n\right)\le 3^{k}T\left(n/2^k\right)+2cn\left({\left(3/2\right)}^k-1\right)$

Substituting $k={\log }_{n}n$ then,

$$\begin{gathered} T\left(n\right)\le n^{{\log }_{2}3}T\left(n/2^{{\log }_{2}n}\right)+2cn\left({\left(3/2\right)}^{{\log }_{2}n}-1\right) \\ \le n^{{\log }_{2}3}T\left(n/2^{{\log }_{2}n}\right)+2cn\left(n^{{\log }_{2}3}/n^{{\log }_{2}2}-1\right) \\ \le n^{{\log }_{2}3}T\left(n/n^1\right)+2cn\left(n^{1.58}/n^1-1\right) \\ \le n^{{\log }_{2}3}T\left(1\right)+2cn\left(\left(n^{1.58}-n\right)/n\right) \\ \le n^{{\log }_{2}3}T\left(1\right)+2cn\left(n^{0.58}/n\right) \\ \le n^{{\log }_{2}3}T\left(1\right)+2c{n}^{0.58} \end{gathered}$$

$T\left(1\right)$can be written as $o\left(1\right)$ and neglect the constant term $2c{n}^{0.58}$. Hence, the above equation becomes,

$$\begin{gathered} T\left(n\right)\le n^{{\log }_{2}3}O\left(1\right) \\ =O\left(n^{{\log }_{2}3}\right) \end{gathered}$$

Therefore, when substituting $k={\log }_{2}n$ in the general representation of $T\left(n\right)$, the final answer $O\left(n^{{\log }_{2}3}\right)$ is obtained.

Solution of part (b)

Finding the general $k$term for the following recurrence:

$T\left(n\right)=T\left(n-1\right)+O\left(1\right)$

Let role="math" localid="1658987670332" $o\left(n\right)\le cn$ thus, $T\left(n\right)$ it will be represented as follows:

$T\left(n\right)\le T\left(n-1\right)+c$

$T\left(n-1\right)$can be represented as follows:

$$\begin{gathered} T\left(n-1\right)\le T\left(\left(n-1\right)-1\right)+c \\ \le T\left(n-2\right)+c \end{gathered}$$

$T\left(n-2\right)$it will be represented as follows:

$$\begin{gathered} T\left(n-2\right)\le T\left(\left(n-2\right)-1\right)+c \\ \le T\left(n-3\right)+c \end{gathered}$$

Substitute equation (2) in equation (1). Hence,$T\left(n\right)$can be rewritten as follows:

$$\begin{gathered} T\left(n-2\right)\le T\left(n-2\right)+c+c \\ \le T\left(n-2\right)+2c \end{gathered}$$

In general,$T\left(n\right)$can be written as follow:

$T\left(n\right)\le T\left(n-k\right)+kc$

Substitute $k=n$ in equation (5),$T\left(n\right)$can be written as follows:

$$\begin{gathered} T\left(n\right)\le T\left(n-n\right)+nc \\ T\left(n\right)=T\left(0\right)+nc \\ =O\left(n\right) \end{gathered}$$

Therefore, $T\left(n\right)=O\left(n\right)$ and it can be obtained by substituting $k=n$.