1
$\begingroup$

I have the Recurrence Relation: $ T(n)=T(log(n))+O(\sqrt{n}) $, and I'm being asked to prove by induction an upper bound. I'm also allowed for ease of analysis to assume $n=2^m$ for some $m$.

So here is a try to prove that $T(n) = O(\sqrt{n})$.

Claim: $\exists_{n_0,c} \forall_{n>n_0}: T(n) \leq c\sqrt{n}$

Proof:

Later, in the inductive step, we will assume that there are $c_1, n_1$ such that $\forall_{n>n_1}: T(log(n)) \leq c_1 \sqrt{log(n)}$.

Also, from the definition of the element $O(\sqrt{n})$ in the original recurrence relation there are $c_2, n_2$ such that $\forall_{n>n_2}: O(\sqrt{n}) \leq c_2 \sqrt{n}$.

Let $n_0 = max\{ 20, n_1, n_2 \}$ (Large enough that $\forall_{n>n_0}: \sqrt{n} \geq \sqrt{log(n)}$).

Let $c=2max \{ c_1,c_2,\frac{T(n_0)}{\sqrt{n_0}} \}$.

Base: For $n_0>1$ we get $T(n_0)=c' \leq c \sqrt{n_0}$.

Step: We assume now that $T(log(n)) =O(\sqrt{log(n)})$, and prove $T(n) =O(\sqrt{n})$

$T(n) = T(log(n))+O(\sqrt{n}) \leq c_1\sqrt{log(n)}+c_2\sqrt{n}$

$ \leq max\{c_1,c_2\}\sqrt{log(n)}+max\{c_1,c_2\}\sqrt{n} = max\{c_1,c_2\}(\sqrt{log(n)}+\sqrt{n})$

$ \leq max\{c_1,c_2\}(\sqrt{n}+\sqrt{n}) = 2max\{c_1,c_2\}\sqrt{n} \leq c\sqrt{n}$, QED.

So my questions are:

  1. Is it a correct proof? Is it true that $T(n) = O(\sqrt{n})$.

  2. Am I allowed to make such an inductive step? I'm used to an inductive step of assuming it is true for $n$, and proving for $n+1$, and here I'm assuming it's true for $log(n)$, and proving for $n$, which seems analogous and the natural "step" of this recurrence relation, but is it correct to do so? It doesn't seem like I proved this for all $n>n_0$. Is it OK because I'm allowed to assume $n=2^m$ for some $m$?

  3. Am I allowed to say in the proof "Later, in the inductive step we will assume that there is $c_1$, so let $c=... c_1 ...$" before reaching this assumption in the inductive step?

Thank you!

$\endgroup$
1
$\begingroup$

Your argument doesn't work. I can't follow it, but you seem to use a different hidden constant for every $n$. Your argument should be a sequence of steps, each following from earlier steps. If you write that later you will do something, this is only to help the reader see what's happening, not a part of the proof.

However, the claim is true: $T(n) = O(\sqrt{n})$. Moreover, if the recurrence is $T(n) \leq T(\log n) + C\sqrt{n}$, then $T(n) \leq C\sqrt{n} + O(\sqrt{\log n})$. A formal proof could go along the following lines:

  1. Argue that $T(n) \leq Cn$. The idea is that $T(n) \leq C\sqrt{n} + C\sqrt{\log n} + \cdots$; each of these summands is at most $C\sqrt{n}$; there are at most $\sqrt{n}$ summands until you reach the base case.

  2. You can now deduce that $T(n) \leq T(\log n) + C\sqrt{n} \leq C\sqrt{n} + C\log n$.

  3. To get even better estimates, open up a few more iterations of the recursion.

$\endgroup$
3
  • $\begingroup$ Thank you very much! Just two points: Why are there at most $\sqrt{n}$ summands? And is $O(\sqrt{n})$ a strict bound or can I get a better one? $\endgroup$ – Ana M Nov 1 '14 at 7:24
  • 1
    $\begingroup$ There are at most $\sqrt{n}$ summands since they decrease by at least $1$ each time (otherwise you get stuck in an infinite loop). About strictness, if $T(n) = T(\log n) + \sqrt{n}$, which satisfies the recursive bound ($T(n) = T(\log n) + O(\sqrt{n})$), then certainly $T(n) \geq \sqrt{n}$, so the solution is tight in general, in the sense that given what you know, you can't get a better bound. $\endgroup$ – Yuval Filmus Nov 1 '14 at 7:39
  • 1
    $\begingroup$ On the other hand, you only have $T(n) = \Omega(\sqrt{n})$ if $T(n) = T(\log n) + \Omega(\sqrt{n})$ (that's actually an if and only if). So it depends on what you assume on your $O(\sqrt{n})$ term. If it is $\Theta(\sqrt{n})$ then you get a tight bound $T(n) = \Theta(\sqrt{n})$. $\endgroup$ – Yuval Filmus Nov 1 '14 at 7:40

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.