Question

solve the following recurrence relations

a. 𝑇(𝑛) = 𝑇( 𝑛/4) + 𝑇( 𝑛/2 ) + 𝑛^2

b. T(n) = T(n/5) + T(4n/5) + n

c. 𝑇(𝑛) = 3𝑇( n/4 ) + 𝑐𝑛^2 

f. 𝑇(𝑛) = (𝑛/𝑛−5) * 𝑇(𝑛 − 1) + 1

g. 𝑇(𝑛) = 𝑇(log 𝑛) + log 𝑛

h. 𝑇(𝑛) = 𝑇 (𝑛^ 1/ 4) + 1

i. 𝑇(𝑛) = 𝑛 + 7 √𝑛 ∙ 𝑇(√𝑛)

j. 𝑇(𝑛) = 𝑇 ( 3𝑛/4 ) + 1/root(n)

Answer 1

a.

so, we have geometric series:

$T(n)=n^2+5n^2/16+25n^2/256+...=n^2/(1-5/16)$

$T(n)=\Theta(n^2)$

c.

Comparing with $T(n)=aT(n/b)+f(n)$ :

$a=3,b=4$

so, we have:

$f(n)=\Omega(n^{log_ba})=\Omega(n^{log_43})$

by Master Theorem:

$T(n)=\Theta(f(n))=\Theta(n^2)$

b.

additive term is exactly the current subproblem size, so T(n) is simply the sum of all numbers that appear in this tree. the:

$T(n)\ge nlog_5n$ and $T(n)\le nlog_{5/2}n$

so,

$T(n)=\Theta(nlogn)$

g.

for recursion tree:

there are $log^*(n)$  levels, and each subproblem at level i has one problem of size $log^{(i)}n$

where $log^{(i+1)}n=log(log^{(i)}n)$ and $log^{(i)}n=logn$

So, the upper bound we have:

$T(n)=logn+T(logn)=O(\displaystyle \sum^{log^*(n)}_{i=0}log^{(i+1)}n)=O(logn)$

This is true because $logn<1/2$ for large n, and $log^{(i+1)}n<\frac{1}{2^i}logn$ and use geometric series. 

Also, $T(n)=\Omega (logn)$

so,

$T(n)=\Theta(logn)$

j.

Comparing with $T(n)=aT(n/b)+f(n)$ :

$a=1,b=4/3$

$f(n)=1/\sqrt n$

so, we have:

$log_ba=log_{4/3}1=0$

$n^{log_ba}=n^{log_{4/3}1}=1$

$f(n)=O(n^{log_ba})=O(n^{log_{4/3}1})=O(1)$

then, by Master Theorem:

$T(n)=\Theta(n^{log_{4/3}1})=\Theta(1)$

h.

$𝑇(𝑛) = 𝑇 (𝑛^{ 1/ 4}) + 1=𝑇 (𝑛^{ 1/ 16}) + 2=𝑇 (𝑛^{ 1/ 64}) + 3=𝑇 (𝑛^{ 1/ 4^n}) + n$

$T(n)=O(n)$

i.

$𝑇(𝑛) = 𝑛 + 7 𝑇(\sqrt𝑛)\sqrt n=7\sqrt n(7T(n^{1/4})n^{1/4}+n^{1/2})+n=$

$=7^kn^{1/2+1/4+1/8+...+1/2^k}T(n^{1/2^k})+...+n$

$1/2+1/4+1/8+...+1/2^k=1-1/2^k$

let $n^{1/2^k}=2$ , then:

$𝑇(𝑛)=7^nT(2)n/2+...+n$

$𝑇(𝑛)=O(7^nn)$

f.

$𝑇(𝑛) = (𝑛/(𝑛−5)) 𝑇(𝑛 − 1) + 1$

$T(n)=(\frac{n}{n-5})^{n-1}T(1)+(\frac{n}{n-5})^{n-2}+...+1$

$T(n)=O(1)$