Big O notation - Proving that a function is not O(n)

Question

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$.

I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$.

Many thanks in advance.

Answer 1

Assuming that $4n2$ means $4n^2$. Recall that something being $O(n)$ means that its absolute avlue is less than $Cn$ for some fixed constant $C$ and for all $n$ (possibly only sufficiently large, depending on your convention) $n$, where $n$ are presumably positive integers.

Now, think about if the inequality $4n^2 \le C n$ can possibly hold for all (sufficiently large) $n$ with one and the same fixed $C$.

Answer 2

Use proof by contradiction: Assume that $4n^2=O(n)~~\forall n\geq 1$, then constant $c$ exist $c<\infty$ such that $4n^2\leq cn$, therefore $n\leq \frac{c}{4}$, since the inequality should hold for all $n$'s, and it doesn't hold for $n=\frac{c}{4}+1$, then there is a contradiction in the initial assumption. Therefore $4n^2\neq O(n)$

Answer 3

Naively $O(n)$ represents functions $f(n)$ such that $\lim_{n\to\infty}|\frac{f(n)}{n}|<\infty$. Since $T(n)=4n^2$,$\lim_{n\to\infty}|\frac{4n^2}{n}|=\lim_{n\to\infty}|4n|=\infty$. So $T(n)$ is not $O(n)$.