# Solving recurrence relation with square n

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{n}) + 2 log(n)\\ &=&T(\sqrt{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.

Thanks

• "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. – Raphael Dec 19 '17 at 16:23

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

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