Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$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.

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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$$

share|improve this answer
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)$$

share|improve this answer
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

Yes!!, the Master Theorem can be applied. I'm going to show you

T(n) = $\sqrt{n}$ T($\sqrt{n}$) + n = $\sqrt{n}$ T($\sqrt{n}$) + O(n)

Let n = $2^k$, $\sqrt{n}$ = $2^{k/2}$, and k = $\log{n}$

T($2^k$) = $2^{k/2}$T($2^{k/2}$) + $2^k$ / dividing by $2^k$

$\frac{T(2^k)}{2^k}$ = $\frac{2^{k/2}T(2^{k/2})}{2^k}$ + 1 (we know that $\frac{2^{k/2}}{2^k}$ = $\frac{1}{2^{k/2}}$ )

$\frac{T(2^k)}{2^k}$ = $\frac{T(2^{k/2})}{2^{k/2}}$ + 1

Let y(k) = $\frac{T(2^k)}{2^k}$, then

y(k) = y($\frac{k}{2}$) + 1

Now, we apply the Master Theorem (T(n) = aT($\frac{n}{b}$) + $n^d$), where a=1, b=2, and d=0, a=$b^d$ = 1

y(k) = $k^d\log{k}$ = $\log{k}$ (because d=0)

But, we also know that T($2^k$) = $2^ky(k)$, then

T($2^k$) = $2^k\log{k}$ = T(n) = $n\log{\log{n}}$ (because n=$2^k$ and k = $\log{n}$)

Finally: T(n) = $\Theta(n\log{\log{n}})$

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.