0
$\begingroup$

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.

Thanks

$\endgroup$
  • $\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 Dec 19 '17 at 16:23
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I can't follow you from "This translates...", why do you use 3 costants? $\endgroup$ – JrHowen Dec 19 '17 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 Dec 19 '17 at 14:50

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.