Extended Master's Theorem $T(n)=n^{1/2}T(n^{1/2})+n$

Question

Can Extended Masters theorem be applied to the following recursive equation ?
$T(n)=n^{1/2}T(n^{1/2})+n$

I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ 

I was wondering if this equation could be solved using masters theorem, like the way Tauhin Gangwar has solved here - https://gateoverflow.in/60532/find-tc-t-n-2t-n-1-2-1

Comments

yes you can apply extended master method for this question too ,

Answer 1

Yes, you can apply master's theorem, but you won't need to when you get to the right form.

Let $n = 2^{k}$. The recurrence becomes : $T( 2^{k}) = 2^{k/2}T( 2^{k/2}) + 2^{k}$. Now divide the entire equation by $2^{k}$. We get :

$T( 2^{k}) / 2^{k}= T( 2^{k/2})/2^{k/2} + 1$ Let $F(k) = T( 2^{k}) / 2^{k}$. Thus, what we have is: $F(k) = F(k/2) + 1$.

Apply master's theorem if you want but why even bother if you know what time is taken by binary search.Cheers.

Comments

Thanks...great help

---

@Daniyal89 yes you can.. it falls under case 3 of generic form of master theorem.. there are plenty of answers on this question on this platform

---

So final answer comes out to be loglogn?