Recurrence

Question

Answer 1

Let $n = 2^m$, Then recurrence becomes $T(2^m) = 2^{\frac{m}{2}}T\left(2^{\frac{m}{2}}\right) + 2^m$ $ \color{green}{(m = \log_2(n))}$

Dividing by $2^m$ we get, $ \frac{T(2^m)}{2^m} = \frac{T\left(2^{\frac{m}{2}}\right)}{2^{\frac{m}{2}}} + 1$

Let $\frac{T(2^m)}{2^m}  = S(m)$

Recurrence becomes, $S(m) = S(\frac{m}{2}) + 1 \color{navy}{\Rightarrow S(m) = \log_2(m)}$

$S(m) = \log_2(m) \Rightarrow T(2^m) = 2^m * S(m)$

Putting $m = \log_2n$, We get $T(n) = 2^{\log_2n}*\log_2(\log_2n) = n*\log_2(\log_2n)$

Thus $\color{red}{T(n) = \theta(n\log \log n)}$

Answer 2

T(n)=n^1/2 T(n^1/2)+n

    =n^1/2[n^1/2 T(n^1/4)+n^1/2]+n

   =n^3/4 T(n^1/4)+n+n

    =n^3/4[n^1/8 T(n^1/8)+n^1/4)+n+n

   =n^7/8 T(n^1/8)+n+n+n

.

.

.

=n^(1-(1/2^k))T(n^1/2^k)+kn

solve this one.

n^(1/2^k)=2  (apply logarithm on both sides)

1/2^k logn=1

k=loglogn.

given equation is=n^(1-(1/logn)).a+n.loglogn

                        =na+n.loglogn

so time complexity is O(nloglogn)