0
$\begingroup$

I need to prove that $T(n)$ is $O(n^2)$ using only the definition of $O$ and induction.
I don't want a solution that "finds" a pattern in $T(n)$.
Here, $T(1)=1$ and $ T(n) = T(n-1) + n $.
By the definition of $O$, we have to prove that: $$ \exists c > 0, n_0 > 0, \ \ T(n) \le cn^2 \ \forall \ n \ge n_0 $$
Let $n_0 = 1.$
I shall try to accomplish this via induction on $n$:
Basis step: $n = 1$
$ T(1) = 1 \le c^2 \ \ \forall c \gt 1 $
Inductive Step:
Inductive Hyposthesis: $T(n) \le cn^2 \ \forall \ n \ge 1 $ for $n = k-1, k-1 \ge 1$.
To prove: $T(n) \le cn^2 \ \forall \ n \ge 1 $ for $n = k$
$$ T(k) = T(k-1) + k $$ $$ T(k) \le c(k-1)^2 + k \hspace{1em} \text{(by the inductive hyposthesis) }$$ $$ T(k) \le ck^2 + (1- 2c)k + c $$ How shall I proceed further with the proof?

$\endgroup$
3
  • $\begingroup$ @Peter I know that would be a much simpler and elegant way of proving the claim, but I specifically want to use the the definition of $O$ (in terms of $c, n_0$) to prove this. $\endgroup$
    – Bingwen
    Sep 14, 2020 at 13:03
  • $\begingroup$ @Peter Sorry, there was an error on my part while typing the question. Have fixed it now, it is $T(n-1) + n$ $\endgroup$
    – Bingwen
    Sep 14, 2020 at 13:13
  • $\begingroup$ $O(n^2)$ does not mean that the function is bounded from above by $n$ times a constant. And in fact, $T(n)$ grows faster than any linear function $an+b$. $\endgroup$
    – Peter
    Sep 14, 2020 at 13:29

1 Answer 1

0
$\begingroup$

Edit: so it is $T(n) = T(n-1) + n = n(n+1)/2$ which is obviously $O(n^2)$. If you want to check it explicitly without using that, you can choose $c=2$ and the induction step would be \begin{align*} T(n) \leq c(n-1)^2 + n = 2n^2 - 3n +2 \leq 2n^2 \end{align*} since $n\geq 1$.

$\endgroup$
1
  • $\begingroup$ Sorry, there was an error on my part while typing the question. Have fixed it now. $\endgroup$
    – Bingwen
    Sep 14, 2020 at 13:12

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.