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 Answer 1

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
    Commented Nov 1, 2014 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$ Commented Nov 1, 2014 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$ Commented Nov 1, 2014 at 7:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .