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 '14 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