# Solve the recurrence relation T(n)=3T(√n)+lg(n) [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

## 1 Answer

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