# Master Theorem for Solving $T(n) = T(\sqrt n) + \Theta(\lg\lg n)$

I'm trying to solve the recurrence relation: $$T(n) = T(\sqrt n) + \Theta(\lg \lg n)$$

My first step was to let $m = \lg n$, making the above: $$T(2^m) = T(2^{m\cdot 1/2}) + \Theta(\lg m)$$

If $S(m) = T(2^m)$, then $$S(m) = S(m/2) + \Theta(\lg m)$$

This is an easier recurrence to solve. If I try and use the Master Theorem, I calculate $n^{\log_b a}$ where $a=1$ and $b=2$ to be $n^0=1$. It seems like this might be case 2 of the Master Theorem where $f(n)= \Theta(n^{\log_b a})$.

For $S(m)$, $\Theta(n^{\log_b a})= \Theta(1)$. But $f(m) = \lg m$. Therefore $f(n) \neq \Theta(n^{\log_b a})$. So it doesn't seem case 2 applies.

If I use case 1 or 3 of the Master Theorem, I have to be sure that $f(n)$ is polynomially smaller or larger than $n^{log_b{a}}$, that is to say $f(n)/n^{\log_b a} \le n^\varepsilon$ for some $\varepsilon > 0$. However, $\lg m/1$ does not meet this requirement either.

There's a solution posted to this problem on the MIT OpenCourseWare website that claims that you may use case-2 of the Master's Theorem. It's

(http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf) as problem 1-2d.

I don't see how the Master Theorem applies to the recurrence $S(m)$. In fact I'm not comfortable with this definition of "polynomially" larger, since traditionally polynomials must have integer exponents. If anyone could shed some light on the matter it would be greatly appreciated!

Thanks!

-
Please excuse my ignorance but the only statement that I'm confused about in the whole ordeal is: If S(m)=T(2^m ) , then S(m)=S(m/2)+Θ(lgm) Could you please explain how you got that? –  Vaibhav Jul 23 at 16:01

Starting where you left off:

$S(m)=S(m/2)+ \Theta(\lg m)$

Compared this to the generic recurrence:

$T(n) = aT(n/b) + f(n)$

Let's address the questions, you raised.

### What does "polynomially" larger mean?

A function $f(n)$ is polynomially larger than another function $g(n)$, if $f(n) = n^i g(n)/t(n)$, where $t(n)$ is some sub-polynomial factor such as $\log n$, etc that appears in $g(n)$. In other words, we want to see, ignoring sub-polynomial and constant factors, if $f(n)$ is a polynomial multiple of $g(n)$.

### Does case 2 apply here?

Recall that Case 2 of the master theorem applies when $f(n)$ is roughly proportional to $n^{\log_b a}\log^kn$ for some $k \ge 0$. Now, applying all this to your equation above, $a = 1$, $b=2$ and $f(m) = \Theta(\log m)$. This give $k = 1$ and since $m^{\log_2 2^0}\log^km = \Theta(\log m)$, case 2 does apply.

### What is the solution using Case 2?

Generally, when case 2 does apply, the solution is always of the form $\Theta(n^{\log_b a}\log^{k+1}n)$. So, in your case, it'll be $\Theta(\log^2 m)$ as you've already figured.

-

Another iteration of your transformation should do it. Let $p=\mathrm{lg}\ m$, $m=2^p$, and $R(p) = S(2^p)$; then the recurrence becomes $R(p) = R(p-1)+\Theta(p)$. Can you work the rest of it from here?

-
Thanks for the response! I can follow your reply through to see that S(m) = lg(m) lg(m), which can be used to yield the final solution O((lg lg n)^2). Your solution is interesting because it very cleanly side-steps using the Master Theorem. However, I still don't understand the assertion in the MIT link that the Master Theorem applies to S(m). Do you understand how it could apply? –  shj Apr 20 '12 at 20:46

Solve the recurrence $T(n) = T(\sqrt{n}) + 2$. Assume that $T(n)$ is constant for $n ≤ 2$.

-
You may want to consider LaTeXing answers in general to make them easier to read. Not really a big deal in this case but very useful in general. –  Tom Oldfield Nov 16 '12 at 0:12
Why would this answer the original question? –  robjohn Nov 16 '12 at 3:04
Following up on robjohn's comment, an answer shouldn't require too much unpacking. It should be more or less comprehensible. I see what you intend, but I've been doing this stuff for almost thirty years. –  Rick Decker Nov 16 '12 at 3:44
Rick need help using Maters Theo rum to Solve the recurrence T(n) = T(√n ) + 2. Assume that T(n) is constant for n ≤ 2. –  Andre Cadogan Nov 17 '12 at 13:20