Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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?

share|improve this answer
    
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
add comment

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

share|improve this answer
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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