Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

Question

The recurrence form of bubble sort is $T(n)=T(n-1)+ n- 1$

How can I prove by induction that this is $\Omega(n^2)$?

I'm stuck with $T(n+1) \geq cn^2 + n = n(cn+1)$

Answer 1

Assuming $T(1)=1$, you can show by induction that $T(n) = \frac{n(n-1)}{2} + 1$.

The base case is trivial since $T(1) = 1 = \frac{1 \cdot 0}{2} + 1$.

As for the inductive step, suppose that the claim holds up to $T(n)$. $\begin{align*} T(n+1) &= T(n) + (n+1) - 1 =\frac{n(n-1)}{2} + 1 + n \\ &= \frac{n^2 -n +2n}{2} + 1 = \frac{n^2 + n}{2} + 1 = \frac{n(n+1)}{2} + 1 \\ &= \frac{(n+1)((n+1) - 1)}{2} + 1. \end{align*} $