Big-O Notation Proof

Question

Given the definition of Big-O, prove that $f(n) = n^2 - n$ is $O(n^2)$.

When I use the given definition, I get $n^2 - n \leq n^2 - n^2$ which means that $n^2 -n \leq 0$, which is not true. Is there some step I'm missing?

Answer 1

We have $$n^2-n \ge n^2-n^2$$ not the opposite.

To prove $f(n)$ is $O(n^2)$.

$$n^2-n \leq n^2$$

Answer 2

The definition that you have stated is incorrect. $f(n)$ is $\mathcal{O}(g(n))$ $\textit{iff}$ there exists a constant $c > 0$ and there exists a value for n, $n_0 > 0$, such that $|f(n)|\leq c\cdot|g(n)|~\forall n \geq n_0$.

In your case, $f(n) = n^2 - n$ and $g(n) = n^2$. Let's use the definition above. $$\begin{align*} |f(n)| &\leq c\cdot|g(n)| \\ |n^2 - n| &\leq c\cdot|n^2| \\ \left|1 - \dfrac{1}{n}\right| &\leq c \\ \end{align*}$$ For $c = 1$ and $n_0 = 1$, the above inequality holds. That means that for any value of $n\geq1$ while $c = 1$, $f(n) = n^2 - n$ is $\mathcal{O}(g(n)) = \mathcal{O}(n^2)$.

Another method to solve this is by using limits. $f(n)$ is $\mathcal{O}(g(n))$ if $\lim_{n\to\infty}\dfrac{f(n)}{g(n)}$ is a finite constant. Let's calculate that for the given $f(n)$ and $g(n)$. $$\lim_{n\to\infty}\dfrac{n^2 - n}{n^2}$$ Using L'Hospital's Rule, $$\lim_{n\to\infty}\dfrac{n^2 - n}{n^2} = \lim_{n\to\infty}\dfrac{2n - 1}{2n} = \lim_{n\to\infty}\dfrac{2}{2} = constant$$ Therefore, again, $f(n) = n^2 - n$ is $\mathcal{O}(g(n)) = \mathcal{O}(n^2)$.