How would we prove $\frac{n^2 - n}{2}$ is $\mathcal{O}(n^2)$?

45 Views Asked by At

Given a runtime of $\frac{n^2 - n}{2}$, how would we prove that the big-O notation is $\mathcal{O}(n^2)$. I want to use the $f(n) = \mathcal{O}(g(n))$ formula.

1

There are 1 best solutions below

0
On

Hint: By showing that

$$\left|\frac{\frac{n^2-n}2}{n^2}\right|\le C$$

for some positive constant $C\in\Bbb R^+$ and all sufficiently large $n$.