Prove that if $T(n) = T(n - 1) + \Theta(n)$, then $T(n) = \Omega(n^2)$

Question

In this question, the top answer shows how to prove that $T(n) = O(n^2)$, but not that $T(n) = \Omega(n^2)$. I am struggling with this last half of the proof.

This is what I get when I try to prove it:

$$ \begin{align} T(n)&= T(n-1)+cn\\ &\geq k(n-1)^2+cn\\ &=kn^2 - 2kn + k + cn \end{align} $$

In order for the proof to work, we need $kn^2 - 2kn + k + cn \geq kn^2$. I try to prove this below:

$$ \begin{align} kn^2 - 2kn + k + cn &\geq kn^2 \\ -2kn + k + cn &\geq 0 \\ k(-2n + 1) &\geq -cn \\ k(2n - 1) &\leq cn \\ k &\leq c* \frac{n}{2n-1} \\ \end{align} $$

I know that the RHS of this equation will always be greater than $\frac{c}{2}$. Thus, if we choose any $k \leq \frac{c}{2}$, that last statement will always be true, and the chain of logic proves $T(n) \geq kn^2$ (thus completing our proof).

Does this look correct?

Answer 1

The main idea seems correct, though you made a slight mistake in the beginning, so I would recommend writing out exactly what properties you are using to prove both of these lines: $$T(n) = T(n-1) + cn$$ $$ \geq k(n-1)^2 + cn .$$

One is incorrect and the other is a part of your strategy.

Answer 2

$T(n) = T(n - 1) + \Theta(n)$ implies $T(n) \ge T(n - 1) + cn$ for some $c$. Now sum both sides: $$ \sum_{n=2}^N T(n) \ge \sum_{n=2}^N (T(n-1) + cn) = \sum_{n=1}^{N-1} T(n) + \sum_{n=2}^N cn $$ and so $$ T(N) \ge \sum_{n=2}^N cn = c \sum_{n=2}^N n = c \dfrac{N^2 + N - 2}{2} > \dfrac{c}{2}N^2 $$