I have the following recursive function:

$$ T(n) = \begin{cases} \theta (1) & \text{if $n$ = 1;}\\ T(\sqrt{n}) + \theta (log(n)) & \text{if n $\geq$ 2}\\ \end{cases} $$

I tried:

\begin{eqnarray*} T(n)&=&T(\sqrt{n}) + log(n)\\ &=&T(\sqrt[4]{n}) + 2 log(n)\\ &=&T(\sqrt[8]{n}) + 3 log(n)\\ \end{eqnarray*}

I can't find a way to solve it without master theorem. Is it possible to solve this with the recursive three method? I don't know when should i stop the recursion.

I've already seen other questions about this topic, but they didn't solve my problem.


  • $\begingroup$ "I've already seen other questions about this topic, but they didn't solve my problem." -- How so? As it stands, this is a duplicate. $\endgroup$
    – Raphael
    Commented Dec 19, 2017 at 16:23

1 Answer 1


The thing to point out is that the $\sqrt{n}$ in the recurrence relation should be interpreted correctly - either you view $T$ as a function defined on $\mathbb{R}_{\geq 1}$, which is bounded near $1$, or you actually understand the $\sqrt{n}$ as the integral part, i.e. $[\sqrt{n}]$.

In the first case, you fix a small neighborhood of $1$ on which the function $T$ is bounded by a fixed constant, and the recurrence stops when $n$ falls into this neighborhood; in the second case, the recurrence simply stops at $n = 1$.

Here I give a solution using the first understanding:

Put $m = \log(n)$ and rewrite the relation as:

$$ S(m)=\begin{cases}\theta(1) & m = 0 \text{ (or better: $m \rightarrow 0$)};\\ S(m/2) + \theta(m) & m > 0, \end{cases} $$ where $S(m)$ is the function defined by $S(\log(n))=T(n)$.

This translates to the following: we have constants $r$, $c$, $d$, such that:

  • $S(m) \leq c$ for all $0 \leq m < r$;
  • $S(m) \leq S(m/2) + d \cdot m$ for all $m \geq r$.

It is then easily proved using induction that we actually have $$ S(m) \leq \max(2c/r, 2d) \cdot m $$ for all $m \geq r/2$. (First note that it is true for $m$ in the interval $[r/2, r)$, and then show that if it is true on the interval $[x/2, x)$, then it is also true on the interval $[x, 2x)$.)

So finally we get $T(n) = \theta(\log(n))$.

  • $\begingroup$ I can't follow you from "This translates...", why do you use 3 costants? $\endgroup$
    – JrHowen
    Commented Dec 19, 2017 at 14:36
  • $\begingroup$ The first line is a re-statement of "$S(m) = \theta(1)$ when $m$ tends to $0$". The second line should be clear. $\endgroup$
    – WhatsUp
    Commented Dec 19, 2017 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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