4-1 Recurrence examples

Give asymptotically tight upper and lower bounds for $T(n)$ in each of the following algorithmic recurrences. Justify your answers.

a. $T(n) = 2T(n/2)+n^3$.

b. $T(n) = T(8n/11)+n$.

c. $T(n) = 16T(n/4)+n^2$.

d. $T(n)=4T(n/2)+n^2\lg n$.

e. $T(n) = 8T(n/3)+n^2$.

f. $T(n)=7T(n/2)+n^2\lg n$.

g. $T(n)=2T(n/4)+\sqrt{n}$.

h. $T(n)=T(n-2)+n^2$.

a

$$ \begin{aligned} n^{\log_{b}a}=n^{\log_{2}2}=n\cr f(n)=n^3=\Omega(n^{2+\log_{b}a})\cr 2f(n/2)=n^3/4\leq \frac{1}{4}f(n)\cr T(n)=\Theta(f(n))=\Theta(n^3)\cr \end{aligned} $$

b

$$ \begin{aligned} n^{\log_{b}a}=n^{\log_{11/8}1}=1\cr f(n)=n=\Omega(n^{1+\log_{b}a})\cr f(8n/11)=8n/11\leq \frac{8}{11}f(n)\cr T(n)=\Theta(f(n))=\Theta(n)\cr \end{aligned} $$

c

$$ \begin{aligned} n^{\log_{b}{a}}=n^{\log_{4}{16}}=n^{2}\cr f(n)=n^2=\Theta(n^{\log_{b}a}\lg^{0}n)\cr T(n)=\Theta(n^2\lg^{} n)\cr \end{aligned} $$

d

$$ \begin{aligned} n^{\log_{b}{a}}=n^{\log_{2}{4}}=n^{2}\cr f(n)=n^2\lg^{} n=\Theta(n^{\log_{b}a}\lg^{}n)\cr T(n)=\Theta(n^2\lg^{2} n)\cr \end{aligned} $$

e

$$ \begin{aligned} n^{\log_{b}{a}}=n^{\log_{3}{8}}\cr f(n)=n^2=\Omega(n^{\log_{b}a})\cr f8(n/3)=\frac{8n^2}{9}\leq \frac{8}{9}f(n)\cr T(n)=\Theta(f(n))=\Theta(n^2)\cr \end{aligned} $$

f

$$ \begin{aligned} n^{\log_{b}{a}}=n^{\log_{2}{7}}\cr f(n)=n^2\lg^{} n=O(n^{\log_{b}a-\log_2{(7/4)}})\cr T(n)=\Theta(n^{\log_{2}{7}})\cr \end{aligned} $$

g

$$ \begin{aligned} n^{\log_{b}{a}}=n^{\log_{4}{2}}=n^{1/2}\cr f(n)=n^{1/2}=\Theta(n^{\log_{b}a}\lg^{0}n)\cr T(n)=\Theta(n^{1/2}\lg^{} n)\cr \end{aligned} $$

h

$$ \begin{aligned} T(n)=\frac{1}{2}\sum_{i=1}^{n}i^2=\Theta(n^3)\cr \end{aligned} $$