4-4 More recurrence examples

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

a. $T(n)=5T(n/3)+n\lg n$.

b. $T(n)=3T(n/3)+n/\lg n$.

c. $T(n)= 8T(n/2)+n^3\sqrt{n}$.

d. $T(n)=2T(n/2-2)+n/2$.

e. $T(n)=2T(n/2)+n/\lg n$.

f. $T(n)=T(n/2)+T(n/4)+T(n/8)+n$.

g. $T(n)=T(n-2)+1/n$.

h. $T(n)=T(n-1)+\lg n$.

i. $T(n)=T(n-2)+1/\lg n$.

j. $T(n)=\sqrt{n}T(\sqrt{n})+n$.

a

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

b

$$ \begin{aligned} & 3(\frac{1}{3})^p=1\cr \implies & p = 1\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & = \Theta(n^1(1+\int_{1}^{n}\frac{x/\lg x}{x^{2}}dx))\cr & = \Theta(n^1(1+\int_{1}^{n}\frac{1}{x^{}\lg x}dx))\cr & = \Theta(n^1(1+\left[\lg\lg x\right]_{1}^{n}))\cr & = \Theta (n\lg\lg n)\cr \end{aligned} $$

• Tips: if $f(1)=\infty$, we will assume $T(1)=f(1)=\Theta(1)$

c

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

d

$$ \begin{aligned} f(n)=n/2 \text{ satisfies polynomial-growth condition}\cr T(n)=2T(n/2)+n/2\cr n^{\log_{b}{a}} = n^{\log_{2}{2}}=n^{}\cr f(n) = n^{}/2 = \Theta(n^{\log_{b}{a}}\lg^{0}n)\cr T(n)=\Theta(n^{\log_{b}{a}}\lg n)=\Theta(n\lg n)\cr \end{aligned} $$

e

$$ \begin{aligned} & 2(\frac{1}{2})^p=1\cr \implies & p = 1\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & = \Theta(n^1(1+\int_{1}^{n}\frac{x/\lg x}{x^{2}}dx))\cr & = \Theta(n^1(1+\int_{1}^{n}\frac{1}{x^{}\lg x}dx))\cr & = \Theta(n^1(1+\left[\lg\lg x\right]_{1}^{n}))\cr & = \Theta(n\lg\lg n)\cr \end{aligned} $$

f

$$ \begin{aligned} & (\frac{1}{2})^{p}+(\frac{1}{4})^{p}+(\frac{1}{8})^{p}=1\cr & 0.5<p<1\cr T(n) & =\Theta(n^p(1+\int_{1}^{n}\frac{f(x)}{x^{p+1}}dx))\cr & = \Theta(n^p(1+\int_{1}^{n}\frac{x}{x^{p+1}}dx))\cr & = \Theta(n^p(1+\int_{1}^{n}\frac{1}{x^{p}}dx))\cr & = \Theta(n^p(1+\left[x^{1-p}\right]_{1}^{n}))\cr & = \Theta(n)\cr \end{aligned} $$

g

$$ \begin{aligned} T(n) & = \frac{1}{2}\sum_{i=1}^{n}(\frac{1}{i})\cr & \leq \frac{1}{2}+1/2\int_{1}^{n-1}\frac{1}{x}\cr & = \Theta(\frac{1}{2}+\frac{1}{2}\lg (n-1))\cr & = \Theta(\lg n)\cr \end{aligned} $$

h

$T(n)=T(n-1)+\lg n$ $$ \begin{aligned} T(n) & = \sum_{i=1}^{n}\lg i\cr & = \lg(n!)\cr & = \Theta(n\lg n)\cr \end{aligned} $$

i

$$ \begin{aligned} T(n) & =1+\sum_{i=2}^{n}\frac{1}{\lg i}\cr & = \Omega(\frac{n^2}{\sum_{i=2}^{n}\lg n})\cr & = \Omega(\frac{n}{\lg n})\cr T(n) & =O(\sum_{i=2}^{\sqrt{n}-1}\frac{1}{\lg 2}+\sum_{i=\sqrt{n}}^{n}\frac{1}{\lg \sqrt{n}})\cr & = O(\sqrt{n}+\frac{n}{\lg n})\cr T(n) & = \Theta(n)\cr \end{aligned} $$

j

depth: $\lg\lg n+1$, leaves: $n$

total cost of over all nodes at depth $i$, for $i=0,1,...,\lg \lg n-1$, is n

$$ \begin{aligned} T(n)=\Theta(n\lg\lg n)\cr \end{aligned} $$