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.

While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen:

Suppose the function $f$ satisfies the recurrence relation $f(n)=2f(\sqrt{n})+\log n$ whenever $n$ is a perfect square greater than 1 and $f(2)=1$.

Find a big-O estimate for $f(n)$ [Hint: Make the substitution $m=\log n$.]

(Note: here, $\log n$ stands for base 2 logarithm of $n$.)

In this solution, I am supposed to use the following variant of the Master Theorem:

Master Theorem. Let $f$ be an increasing function that satisfies the recurrence relation

$$f(n)=af(n/b)+cn^d$$

whenever $n=b^k$, where $k$ is a positive integer, $a\geq 1$, $b$ is an integer greater than 1, and $c$ and $d$ are real numbers with $c$ postive and $d$ nonnegative. Then

$$\begin{align}f(n)&\text{is }\begin{cases} O(n^d)&\text{ if $a < b^d$,} \\ O(n^d\log n)&\text{ if $a = b^d$,} \\ O(n^{\log_b a})&\text{ if $a > b^d$.} \end{cases}\end{align}$$

I solved it as follows, but I'm not sure if this is correct:

Following the hint given, I made the substitution $m = \log n$. Then, $n=2^m$. Rewriting the recurrence relation with this value for $n$:

$$f(2^m)=2f(\sqrt{2^m})+\log (2^m)\text{ with }f(2)=1$$

$$f(2^m)=2f(2^{m/2})+m\text{ with }f(2)=1$$

(because $\sqrt{2^m}=2^{m/2}$ and $\log (2^m)=m$.)

To simplify the analysis, I will rewrite the recurrence relation above for $T(m)=f(2^m)$:

$$T(m)=2T(\dfrac{m}{2})+m\text{ with }T(1)=1$$

Now I will apply the Master Theorem for $T(m)$. In this case, $d=1$, $b=2$ and $a=2$, this recurrence relation meets the condition $a=b^d$ in the Master Theorem; therefore:

$$T(m)\text{ is }O(m^d\log m)=O(m\log m)$$

Now I will rewrite the estimate above in terms of $f(n)$, substituting $T(m)=f(2^m)=f(2^{\log n})=f(n)$ and $m=\log n$:

$$f(n)\text{ is } O(\log n\log \log n)$$

Is this solution correct? If yes, is there any way to simplify it further?

share|improve this question
    
Is $f(n)$ well defined when $n\neq2$ is not a perfect square? –  Frank Science Jul 15 '12 at 2:55
    
@FrankScience: In this exercise, it seems that it's not. –  anonymous Jul 15 '12 at 22:33

1 Answer 1

up vote 7 down vote accepted

Let's use recursion trees (otherwise known as "the proof of the Master theorem")!

  • The root of the recursion tree for $f(n)$ has value $\log n$.

  • Each child of the root has value $\log \sqrt{n} = (\log n)/2$, so the total value of all nodes at depth $1$ is also $\log n$.

  • (Sanity check:) Each grandchild of the root has value $\log \sqrt{\sqrt{n}} = (\log n)/4$. So the total value of all $4$ nodes at level $2$ is also $\log n$.

  • An easy inductive argument implies that for any $\ell$, the total value of the $2^\ell$ nodes at level $\ell$ is $\log n$.

  • Thus, all level sums are identical, which implies that $f(n) = \Theta(L\log n)$, where $L$ is the number of levels.

  • Another easy inductive argument implies that each subtree rooted at level $L$ represents the function $f(n^{2^{-L}})$. So the recursion bottoms out at the smallest level $L$ such that $n^{2^{-L}} \le 2$. (There's nothing special about the number 2 here; any constant larger than 1 will do.) We have $$ n^{2^{-L}} \le 2 \iff 2^{-L}\log n \le 1 \iff \log n \le 2^L \iff L \le \log\log n. $$

  • We conclude that $f(n) = \Theta(\log n \log \log n)$.

share|improve this answer
    
+1 for this alternative solution, although I am not familiar with this recursion tree technique. –  anonymous Jul 15 '12 at 15:41

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.