This question already has an answer here:

Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem. So, how I will find Θ of T(n)?


marked as duplicate by David Richerby, Apass.Jack, Evil, Yuval Filmus algorithms Feb 7 at 5:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Define $X(n) = T (2^n)$.

Then $X(n) = T (2^n) = 3T(2^{n/2}) + n = 3X(n/2) + n$.

You solve the recurrence for $X(n)$, and $T(m) = X (\log m)$.


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