Proving a Recurrence Relation by induction

Question

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!

Answer 1

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.