snippetModerate
How to solve T(n)=2T(√n)+log n with the master theorem?
Viewed 0 times
thelogwithmastersolvetheoremhow
Problem
I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?
Solution
Let us actually use the master theorem.
Define $S(n) = T(e^n)$ for all $n$. Then
$$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$
Now we can apply the second case of the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain
$$ S(n) = \Theta(n\log n)$$
So for $n\gt0$,
$$ T(n) = S(\log n) = \Theta(\log n \log\log n)$$
Define $S(n) = T(e^n)$ for all $n$. Then
$$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$
Now we can apply the second case of the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain
$$ S(n) = \Theta(n\log n)$$
So for $n\gt0$,
$$ T(n) = S(\log n) = \Theta(\log n \log\log n)$$
Context
StackExchange Computer Science Q#96422, answer score: 10
Revisions (0)
No revisions yet.