# Solve the recurrence relation:$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$

$$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$$

Master method does not apply here. Recursion tree goes a long way. Iteration method would be preferable.

The answer is $Θ (n \log \log n)$.

Can anyone arrive at the solution.

-

Let $n = m^{2^k}$. We then get that $$T(m^{2^k}) = m^{2^{k-1}} T (m^{2^{k-1}}) + m^{2^{k}}$$ \begin{align} f_m(k) & = m^{2^{k-1}} f_m(k-1) + m^{2^k} = m^{2^{k-1}}(m^{2^{k-2}} f_m(k-2) + m^{2^{k-1}}) + m^{2^k}\\ & = 2 m^{2^k} + m^{3 \cdot 2^{k-2}} f_m(k-2) \end{align} $$m^{3 \cdot 2^{k-2}} f_m(k-2) = m^{3 \cdot 2^{k-2}} (m^{2^{k-3}} f_m(k-3) + m^{2^{k-2}}) = m^{2^k} + m^{7 \cdot 2^{k-3}} f_m(k-3)$$ Hence, $$f_m(k) = 2 m^{2^k} + m^{3 \cdot 2^{k-2}} f_m(k-2) = 3m^{2^k} + m^{7 \cdot 2^{k-3}} f_m(k-3)$$ In general, it is not hard to see that $$f_m(k) = \ell m^{2^k} + m^{(2^{\ell}-1)2^{k-\ell}} f_m(k-\ell)$$ $\ell$ can go up to $k$, to give us $$f_m(k) = km^{2^k} + m^{(2^{k}-1)} f_m(0) = km^{2^k} + m^{(2^{k}-1)} m^{2^0} = (k+1) m^{2^k}$$ This gives us $$f_m(k) = (k+1) m^{2^k} = n \left(\log_2(\log_m n) + 1\right) = \mathcal{O}(n \log_2(\log_2 n))$$ since $$n=m^{2^k} \implies \log_m(n) = 2^k \implies \log_2(\log_m(n)) = k$$

-
Thanks Marvis. But how did log appear suddenly. Are there some more steps in between. –  VISHNU VIVEK Nov 17 '12 at 18:56
@VISHNUVIVEK I have added some more details. Hope it is clear now. –  user17762 Nov 17 '12 at 19:12
I appreciate your effort Marvis. I have a question for you. Is it possible to determine the base-case for a recurrence problem if it is not given in the question. Some say that it is not possible to solve recurrence problems if the base-case is not given. In this problem, we have to assume that the base case is T(2)=2. How did you solve it without knowing it. In the answer by Amr, he has left it at the end as T(2). Thus if we substitute T(2)=2, we almost arrive at the answer. –  VISHNU VIVEK Nov 17 '12 at 22:47
@VISHNUVIVEK The base case is $\mathcal{O}(1)$ and hence it typically won't affect the overall order. For instance, as Amr has shown that $$T(m) = m \left(\log_2 \log_2 (m) + \dfrac{T(2)}2 \right)$$ $T(2)$ is just a constant say $T(2) = k$. Hence, the overall cost is $$T(m) = m \left(\log_2 \log_2 (m) + \dfrac{k}2 \right) = \mathcal{O}(m \log_2 \log_2 m)$$ –  user17762 Nov 17 '12 at 22:50
Oh! I almost forgot the fact that it was a constant term. Great. Thanks buddy. –  VISHNU VIVEK Nov 17 '12 at 22:58

Let $n=2^{2^u}$, thus we get: $$T(2^{2^u})=2^{2^{u-1}}T(2^{2^{u-1}})+2^{2^{u}}$$ Now divide both sides by $2^{2^u}$ to get (Note that $2^{2^{u-1}}/2^{2^u}=2^{-2^{u-1}}$) $$2^{-2^u}T(2^{2^u})=2^{-2^{u-1}}T(2^{2^{u-1}})+1$$ $$2^{-2^u}T(2^{2^u})-2^{-2^{u-1}}T(2^{2^{u-1}})=1$$ By summing from 1 to n we get: $$2^{-2^n}T(2^{2^n})-2^{-1}T(2)=n$$ therefore: $$T(2^{2^n})=2^{2^n}(2^{-1}T(2)+n)$$

-
Thanks Amr.. can u pls arrive till the answer which I've prescribed. –  VISHNU VIVEK Nov 17 '12 at 18:52
Actually I don't know the definitions of big O and theta (which you have). That's why I stopped here. I know they are used a lot in CS, but my field is not CS –  Amr Nov 17 '12 at 18:53
The other answer has the big O notation. I think you might want to see this answer. –  Amr Nov 17 '12 at 18:55
Actually your answer is quite understandable. I have a question for you. Is it possible to determine the base-case for a recurrence problem if it is not given in the question. –  VISHNU VIVEK Nov 17 '12 at 19:04