Solving recurrence using recurrence trees.

Question

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this:

$$T(n) = T(\sqrt n) + \lg n$$

If I understand correctly, the recurrence tree method involves looking for the term that moves towards 1 the fastest, find a general formula for this term, then set it equal to 1 and solve it.

Looking at the pattern I found that it should satisfy this equation:

$$n^\frac{1}{2^k} = 1$$

Where $k$ is the tree-level. Further solving gives me:

$$2^k = \log(n-1)$$ $$k = \frac{\log(\log(n-1))}{\log(2)}$$

Now, if I wouldn't have known that the solution is $O(\lg n)$, my best guess in this situation would probably be $O(\lg \lg n)$.

Can somebody please help me understand how to properly analyze this equation?

Answer 1

Here, if you substitute $n = 2^m$, equation becomes, $$ T(2^m) = T(2^{m/2})+ m,$$ Now substitute again, S(m) = $ T(2^m)$, so equation turns to $$ S(m) = S(m/2) + m $$ Now this can be solved using Masters method.

As you mentioned I try to solve that way, I am not very sure if its right still this might help, you can see the term $\sqrt n $ can't be brought down to 1, it can be brought closer to 1 , so if we define our function as \begin{align} \ T(n) & = T(\sqrt n) + logn,\quad if \; n>2 \\ & = 1 \qquad \qquad \qquad if \; n\le 2\\ \end{align}

So we have a tree rooted at n, with branching factor of 1 and work done at each level is $ log n^{1/2^k} $,
Now if we take $ 1/2^k = m $ , so this T(n) terminates when $ n^m = 2 $ On solving it we get k = $ loglog_2n$

So the total work done by T(n) would be $log n + log n^{1/2} + log n^{1/4} + \ldots + log n ^{log log_2 n} $, then

T(n) = $ logn^{1 + 1/2 + 1/4 + \ldots + loglog_2n} $

Answer 2

I'm using Master theorem to solve this recurrence relation.

Given recurrence relation is :

$$T(n) = T(\sqrt{n}) + lg(n)$$

$$T(n) = T(\sqrt{n}) + costant.log(n)$$

$$T(n) = T(n^{1/2}) + log(n)$$

Let $k = log(n)$, then $n = 2^k$, so

$$T(2^k) = T(2^{k/2}) + k$$

Assume, $T(2^k) = S(k)$, so $T(2^{k/2}) = S(k/2)$, Then recurrence relation became

$$S(k) = S(k/2) + k$$

The master theorem concerns recurrence relations of the form:

$$T(n) = aT(n/b) + f(n)$$ where $a \geq 1 , b>1$

Now using Master theorem case $(3)$

If $f(n) = \Omega(n^c)$, where $c < log_b(a)$ and if it is also true that:

$af(n/b) \leq kf(n)$ for some constant $k < 1$ and sufficiently large $n$ (often called the regularity condition). Then :

$$T(n) = \Theta(f(n))$$

Therefore,

$k = \Omega(k^c)$, where $c < log_2(1)$

Then : $$S(k) = \Theta(k)$$

$$T(n) = \Theta(log_2(n))$$