Question

Question: Solve the following recurrence relations and give a bound for each of them.

$$\begin{gathered} \mathbf{\left(}\mathit{a}\mathbf{\right)}\mathbf{}\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{2}\mathit{T}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{3}\mathbf{)}\mathbf{+}\mathbf{1} \\ \mathbf{\left(}\mathit{b}\mathbf{\right)}\mathbf{}\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{5}\mathit{T}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{4}\mathbf{)}\mathbf{+}\mathit{n} \\ \mathbf{\left(}\mathit{c}\mathbf{\right)}\mathbf{}\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{7}\mathit{T}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{7}\mathbf{)}\mathbf{+}\mathit{n} \\ \mathbf{\left(}\mathit{d}\mathbf{\right)}\mathbf{}\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{9}\mathit{T}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{3}\mathbf{)}\mathbf{+}{\mathit{n}}^{\mathbf{2}} \\ \mathbf{\left(}\mathit{e}\mathbf{\right)}\mathbf{}\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{8}\mathit{T}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{2}\mathbf{)}\mathbf{+}{\mathit{n}}^{\mathbf{3}} \\ \mathbf{\left(}\mathit{f}\mathbf{\right)}\mathbf{}\mathit{T}\mathbf{\left(}\mathit{n}\mathbf{\right)}\mathbf{=}\mathbf{49}\mathit{T}\mathbf{(}\mathit{n}\mathbf{/}\mathbf{25}\mathbf{)}\mathbf{+}{\mathit{n}}^{\mathbf{(}}\mathbf{3}\mathbf{/}\mathbf{2}\mathbf{\left)}\mathit{l}\mathit{o}\mathit{g}\mathit{n} \\ \mathbf{\right(}\mathit{g}\mathbf{)}\mathbf{}\mathit{T}\mathbf{(}\mathit{n}\mathbf{)}\mathbf{=}\mathit{T}\mathbf{(}\mathit{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{+}\mathbf{2} \\ \mathbf{(}\mathit{h}\mathbf{)}\mathbf{}\mathit{T}\mathbf{(}\mathit{n}\mathbf{)}\mathbf{=}\mathit{T}\mathbf{(}\mathit{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{+}{\mathit{n}}^{\mathbf{c}}\mathbf{,}\mathit{w}\mathit{h}\mathit{e}\mathit{r}\mathit{e}\mathit{i}\mathit{s}\mathit{a}\mathit{c}\mathit{o}\mathit{n}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{t} \\ \mathbf{(}\mathit{i}\mathbf{)}\mathbf{}\mathit{T}\mathbf{(}\mathit{n}\mathbf{)}\mathbf{=}\mathit{T}\mathbf{(}\mathit{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{+}{\mathit{c}}^{\mathbf{n}}\mathbf{,}\mathit{w}\mathit{h}\mathit{e}\mathit{r}\mathit{e}\mathit{i}\mathit{s}\mathit{s}\mathit{o}\mathit{m}\mathit{e}\mathit{c}\mathit{o}\mathit{n}\mathit{s}\mathit{t}\mathit{a}\mathit{n}\mathit{t} \\ \mathbf{(}\mathit{j}\mathbf{)}\mathbf{}\mathit{T}\mathbf{(}\mathit{n}\mathbf{)}\mathbf{=}\mathbf{2}\mathit{T}\mathbf{(}\mathit{n}\mathbf{-}\mathbf{1}\mathbf{)}\mathbf{+}\mathbf{1} \\ \mathbf{(}\mathit{k}\mathbf{)}\mathbf{}\mathit{T}\mathbf{(}\mathit{n}\mathbf{)}\mathbf{=}\mathit{T}\mathbf{(}\mathbf{\surd }\mathit{n}\mathbf{)}\mathbf{+}\mathbf{1} \end{gathered}$$

Short answer

$\theta$bound for each recurrence relation is as follows:

$$\begin{gathered} \left(a\right)O\left(n^{lo{g}_{3}2}\right) \\ \left(b\right)O(n^{lo{g}_{4}5} \\ \left(c\right)O(nlogn) \\ \left(d\right)O(n^{2}logn) \\ \left(e\right)O(n^{2}logn) \\ \left(d\right)O(n^{\frac{3}{2}}logn) \\ \left(e\right)O(n) \\ \left(f\right)O(n^{c+1}) \\ \left(g\right)O(c^n) \\ \left(h\right)O(2^n) \\ \left(i\right)O(log\left(logn\right)) \end{gathered}$$

Step-by-step solution

Introduction

In above question there will be total a to k different formula theorem. Which we have to make it correct as per the calculation process is given and on that base we have to write answer base on the calculation of program is written during calculation.

To see all the calculation with given formulation check step-2 as below.

Calculation of  Θ bound

$O(\log \log n)$$T(n-2)$(a)

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

Evaluate the two recurrence equation's master theorem.

localid="1658923707909" $T\left(n\right)=aT(n/b)+n^c$ ---(2)

By simply compare & calculate equation (1) and (2), the value of

$“n^C”is“1”,“c”is“0”,“b”is“3”\&“a”is“2”.$

By master’s theorem, if the value of then the running time is,

$T\left(n\right)=O\left({n^{{\log }_b}}^a\right)$ ---(3)

Here, the value of $lo{g}_{b}a=lo{g}_{3}2=063092$and it is greater than “c”.

Substitute the values of “b” as 3 and “a” as 2 in equation (3). So the running time of algorithm is,

localid="1658923595278" $T\left(n\right)=O{n}^{log{3}^2}$

Therefore, the algorithm takes a run time of: localid="1658924131831" $O\left(n^{\log 3^2}\right)$.

(b)

$T\left(n\right)=5T(n/4)+n$ ---(1)

Consider the master theorem for the following recurrence equation,

$T\left(n\right)=aT(n/b)+n^c$ ---(2)

By equality of calculation of equation (1) and (2), the value of $“n^c”is“nn”,“c”is“1”,bis“4”and“aa”is“5”.$

By main theorem, if the value of $c<lo{g_b}^a$, running time is,

localid="1658924099025" $T\left(n\right)=O{n}^{lo{g_b}^a}$ ---(3)

Here, the number of $lo{g_b}^a=lo{g}_{4}5=1.160963$and it’s bigger than “ c ”.

Extra/substitute the detail of “ b ” as 4 and “ a ” as 5 in equation (3). Thus, time is going for algorithm,

localid="1658924202541" $T\left(n\right)=O{n}^{lo{g_5}^4}$

As a result, the method requires a run time of localid="1658924182217" $O\left(n^{{{\log }_4}^5}\right)$.

(c)

$T\left(n\right)=7T(n/7)+n$

Check out the following recurrence equation's governing theorem:

$T\left(n\right)=aT(n/b)+n^c$ ----- (2)

The amount of may be determined by comparing equations (1) and (2). $“n^c”is“n”,cis“1”,“b”is“7”and“a”is“7”.$

By master’s theorem, if the value of $c=lo{g}_{b}a,$,then the running time is,

$T\left(n\right)=O\left(n^{c}logn\right)$ ---(3)

Here, the value of and it is equal to “ ”.

Substitute the value of “c ” as in equation (3). So the running time of algorithm is,

$$\begin{gathered} T\left(n\right)=(n^{3}logn) \\ O(n\log n) \end{gathered}$$

Therefore, the algorithm takes a run time of $O(n\log n)$.

(d)

The recurrence relation is shown below:

$T\left(n\right)=9T(n/3)+n^2$ ----(1).

Check out the following recurrence equation's governing theorem,

$T\left(n\right)=aT(n/b)+n^2$ ----(2)

By equally manage equation with calculation of (1) and (2), the value of $n^c”is“n^2”,“c”is“2”,“b”is3and“a”is9.$

By main theorem, if the amount of , then the time is going,

$T\left(n\right)=O(n^{c}logn)$ ----(3)

Here, the value of $lo{g}_{b}a=lo{g}_{3}9=2$ and it is equal to “ c ”.

In the equation, replace "c " with " 2 " (3). As a result, the algorithm's execution time is

$T\left(n\right)=O\left(n^{2}logn\right)$

Therefore, the algorithm takes a run time of $O\left(n^{2}logn\right).$.

(e)

The recurrence relation is shown below:

$T\left(n\right)=8T(n/2)+n^3$ ----(1)

Consider the following recurrence equation's master theorem

$T\left(n\right)=aT(n/b)+n^2$ ----(2)

The value of may be determined by comparing equations (1) and (2) .

$“n^c”is“”,“c”is3,“b”is“2”and“a”is8.$

According to the master's theorem, if the value of $c=lo{g}_{b}a$, then the running time is,

$T\left(n\right)=O(n^{c}logn)$ ----(3)

Here, the value $lo{g}_{b}a=lo{g}_{b}8=3$of and it is equal to “c ”.

In equation, change the value of "c " to 3. (3). As a result, the algorithm's execution time is

$T\left(n\right)=O\left(n^{3}logn\right)$

Therefore, the algorithm takes a run time of .

(f)

The recurrence relation is shown below:

localid="1658980924866" $T\left(n\right)=49(n/25)+n^{\frac{3}{2}logn}$ ----(1)

Consider the master theorem for the following recurrence equation,

$T\left(n\right)=aT(n/b)+n^2$ ----(2)

By comparing equation (1) and (2), the value of $“n^c”is{n}^{\frac{3}{2}logn},“c”islogn=1.5logn,“b”is25and“a”is.$

By master’s theorem, if the value of $c>lo{g}_{b}a,$, then the running time is,

$T\left(n\right)=O\left(n^c\right)$ ----(3)

The value of $lo{g}_{b}a=lo{g}_{25}49=1.209062$ is less than the value of “c ” is $1.5\log n.$.

Substitute the value of “c ” as $\frac{3}{2}\log n$ in equation (3). So the running time of algorithm is localid="1658981448371" $T\left(n\right)=O\left(n^{\frac{3}{2}logn}\right)$.

Therefore, the algorithm takes a run time of $O\left(n^{\frac{3}{2}logn}\right)$

(g)

$$\begin{gathered} T\left(n\right)=T(n-1)+2........\left(1\right) \\ T(n-1)canberepresentedasfollows: \\ T(n-1)=T\left(\right(n-1)-1)+2 \\ =T(n-2)+2.......\left(2\right) \\ T(n-2)canberepresentedasfollows: \\ T(n-2)=T\left(\right(n-2)-1)+2 \\ =T(n-3)+2.......\left(3\right) \\ T(n-3)canberepresentedasfollows: \\ T(n-3)=T\left(\right(n-3)-1)+2 \\ =T(n-4)+2..........\left(4\right) \end{gathered}$$

Substitute equation (2) in equation (1). Hence, can be rewritten as follows:

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

----(5)

Substitute equation (3) in equation (5).

$$\begin{gathered} T\left(n\right)=T(n-3)+2+4 \\ =T(n-3)+6 \end{gathered}$$ ----(6)

Substitute equation (4) in equation (6).

$$\begin{gathered} T\left(n\right)=T(n-4)+2+6 \\ =T(n-4)+8 \end{gathered}$$ ----(7)

In general, can be written as follow:

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

Substitute the value of then equation (8) can be represented as follows:

$T\left(n\right)=T\left(0\right)+nc$ ----(9)

Let $T\left(0\right)=1$. Thus, the running of (n) depends only on the value of “ n ” which is as follows:

$$\begin{gathered} T\left(n\right)=1+nc \\ =O\left(n\right) \\ Therefore,T\left(n\right)=O\left(n\right) \end{gathered}$$

(h)

$$\begin{gathered} T\left(n\right)=T(n-1)+n^c............\left(1\right) \\ T(n-1)canberepresentedasfollows: \\ T(n-1)=T\left(\right(n-1)-1)+n^c=T(n-2)+n^c.......(2 \end{gathered}$$

$T(n-2)$can be represented as follows:

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

$T(n-3)$ can be represented as follows:

$$\begin{gathered} T(n-3)=T\left(\right(n-3)-1)+n^c \\ =T(n-4)+n^c \end{gathered}$$ ----(4)

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

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

Substitute equation (3) in equation (5)

$$\begin{gathered} T\left(n\right)=T(n-3)+n^c+2n^c \\ =T(n-3)+3n^c \end{gathered}$$ ----(6)

Substitute equation (4) in equation (6).

$$\begin{gathered} T\left(n\right)=T(n-4)+n^c+3n^c \\ =T(n-4)+4n^c \end{gathered}$$ ----(7)

In general, T(n) can be written as follow:

$T\left(n\right)=T(n-k)+k{n}^c$ ----(8)

Substitute k=n then equation (8) can be represented as follows:

$$\begin{gathered} T\left(n\right)=T(n-n)+n.n^c \\ =T\left(0\right)+n^{(}c+1) \end{gathered}$$ ----(9)

Let $T\left(0\right)=1$. Thus, the running of T(n) depends only on the value of “n ” which is as follows:

$$\begin{gathered} T\left(n\right)=1+\left(n^{c+1}\right) \\ =O\left(n^{c+1}\right) \\ Therefore,T\left(n\right)=O\left(n^{c+1}\right) \end{gathered}$$

(i)

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

T(n-1) can be represented as follows:

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

----(2)

T(n-2) can be represented as follows:

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

----(3)

T(n-3) can be represented as follows:

$$\begin{gathered} T(n-3)=T\left(\right(n-3)-1)+c^n \\ =T(n-4)+c^n \end{gathered}$$

----(4)

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

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

Substitute equation (3) in equation (5).

$$\begin{gathered} T\left(n\right)=T(n-3)+c^n+2c^n \\ =T(n-3)+3c^n \end{gathered}$$ ----(6)

Substitute equation (4) in equation (6).

$$\begin{gathered} T\left(n\right)=T(n-3)+c^n+3c^n \\ =T(n-4)+4c^n \end{gathered}$$ ----(7)

In general, T(n) can be written as follow:

$T\left(n\right)=T(n-k)+\sum _{i=1}^n{c}^i$ ----(8)

Substitute then equation (8) can be represented as follows:

$$\begin{gathered} T\left(n\right)=T\left(0\right)+\sum _{i=1}^n{c}^i \\ =T\left(0\right)+c^0+c^1+...+c^n \\ =T\left(0\right)+(c^{(}n+1)-1)/(c-1) \end{gathered}$$

Note:

The geometric progression of $c^0+c^1+...+c^n$ can be represented as $\frac{c^{n+1}-1}{c-1}$.

Let $T\left(0\right)=1$. Thus, the running of T(n depends only on the value of “$c^n$” which is as follows:

$$\begin{gathered} T\left(n\right)=1+c^n \\ =O\left(c^n\right) \\ Therefore,T\left(n\right)=O\left(c^n\right) \end{gathered}$$ ----(9)

(j)

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

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

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

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

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

$T(n-3)$can be represented as follows:

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

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

$$\begin{gathered} T\left(n\right)=2T(n-1)+1 \\ =2\left(2T\right(n-2)+1)+1 \\ =4T(n-2)+3 \end{gathered}$$ ----(5)

Substitute equation (3) in equation (5)

$$\begin{gathered} T\left(n\right)=4T(n-2)+3 \\ =4\left(2T\right(n-3)+1)+3 \\ =8T(n-3)+4+3 \\ =8T(n-3)+7 \end{gathered}$$

----(6)

Substitute equation (4) in equation (6).

$$\begin{gathered} T\left(n\right)=8T(n-3)+7 \\ =8\left(2T\right(n-4)+1)+7 \\ =16T(n-4)+8+7 \\ =16T(n-4)+15 \end{gathered}$$ ----(7)

In general, can be written as follow:

$T\left(n\right)\le 2^{k}T(n-k)+\sum _{i=1}^{n-1}{2}^i$ ----(8)

Substitute then equation (8) can be represented as follows:

localid="1658985502639" $$\begin{gathered} T\left(n\right)=2^{n}T\left(0\right)+\sum _{i=1}^{n-1}{2}^i \\ =2^{n}T\left(0\right)+2^0+2^1+...+2^{n-1} \\ =2^{n}T\left(0\right)+\frac{2^n-1}{2-1} \end{gathered}$$

Note:

The geometric progression of $2^0+2^1+...+2^{n-1}$can be represented as $\frac{2^n-1}{2-1}$.

Let$T\left(0\right)=1.$.

Thus, the running of T(n) depends only on the value of “ $2^n$” which is as follows:

$$\begin{gathered} T\left(n\right)=2^n+2^n-1 \\ =O\left(2^n\right) \\ Therefore,T\left(n\right)=O\left(2^n\right) \end{gathered}$$

(k)

The recurrence relation is shown below:

$$\begin{gathered} T\left(n\right)=T\left(\sqrt{n}\right)+1 \\ =T\left(n^{\frac{1}{2}}\right)+1 \end{gathered}$$ ----(1)

$T\left(n^{\frac{1}{2}}\right)$ can be represented as follows:

$$\begin{gathered} T\left(n^{\frac{1}{2}}\right)=\left(T(n^{\frac{1}{2})}\right)+1 \\ =T\left(n^{\frac{1}{4}}\right)+1 \end{gathered}$$ ----(2)

$T\left(n^{\frac{1}{4}}\right)$ can be represented as follows:

$$\begin{gathered} T\left(n^{\frac{1}{4}}\right)=T\left(n^{\frac{1}{4}}\right)+1 \\ =T\left(n^{\frac{1}{8}}\right)+1 \end{gathered}$$ ----(3)

$T\left(n^{\frac{1}{8}}\right)$can be represented as follows:

$$\begin{gathered} T\left(n^{\frac{1}{8}}\right)=T\left(n^{\frac{1}{8}}\right)+1 \\ =T\left(n^{\frac{1}{16}}\right)+1 \end{gathered}$$ ----(4)

Substitute equation (2) in equation (1). Hence, can be rewritten as follows:

$$\begin{gathered} T\left(n\right)=T\left(n^{\frac{1}{4}}\right)+2 \\ =\left(T\left(n^{\frac{1}{8}}\right)+1\right)+2 \\ =T\left(n^{\frac{1}{8}}\right)+3 \end{gathered}$$ ----(5)

Substitute equation (3) in equation (5).

$$\begin{gathered} T\left(n\right)=T\left(n^{\frac{1}{4}}\right)+2 \\ =\left(T\left(n^{\frac{1}{8}}\right)+1\right)+2 \\ =T\left(n^{\frac{1}{8}}\right)+3 \end{gathered}$$ ----(6)

Substitute equation (4) in equation (6).

$$\begin{gathered} T\left(n\right)=T\left(n^{\frac{1}{8}}\right)+2 \\ =\left(T\left(n^{\frac{1}{16}}\right)+1\right)+3 \\ =T\left(n^{\frac{1}{16}}\right)+4 \end{gathered}$$ ----(7)

In commonly, been written as follow:

$T\left(n\right)=T\left(n^{\frac{1}{2^k}}\right)+k$ ----(8)

The equation (8) can be represented as follows:

$T\left(n\right)=b+k$

Here, the small continue $n^{\frac{1}{2}}$ is expressed as b & it’s define size of base case. Thus, k is similar to role="math" localid="1658986822994" $O(\log \log n).$

Going time for algorithm is $T\left(n\right)=O(\log \log n)$

So, here algorithm takes time for $O(\log \log n)$.