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?


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} $


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))$$


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

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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