Problem Detail: How to solve the recurrence relation below? $$T(n) = begin{cases} 2T(sqrt{n}) + log n/loglog n & text{if } n > 4 1 & text{if } n leq 4. end{cases}$$ Preferably by the master theorem; otherwise by any method. I know the Master Theorem fails, but is there any extension for these type of problems?
Asked By : WSS
Answered By : Yuval Filmus
Following Timot’s suggestion, let $S(m) = T(2^m)$, so that $S$ satisfies the recurrence $$ S(m) = begin{cases} 2S(m/2) + tfrac{m}{log m} & text{ if } m > 2 1 & text{ otherwise.} end{cases} $$ In fact, we’ll analyze the recurrence with a base case of $m = 1$ instead, and assume the logarithm is base $2$. We have $$ begin{align*} S(2^k) &= frac{2^k}{k} + 2 frac{2^{k-1}}{k-1} + 4 frac{2^{k-2}}{k-2} + cdots + 2^{k-1} frac{2^1}{1} + 2^k &= 2^k left[ frac{1}{k} + frac{1}{k-1} + cdots + frac{1}{1} + 1 right] = Theta(2^klog k). end{align*} $$ Therefore $S(m) = Theta(mloglog m)$ and $T(n) = Theta(log nlogloglog n)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14655 Ask a Question Download Related Notes/Documents
