From the definition of big oh: We say that "$f(n)$ is big oh $g(n)$" if there exists an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$.
Substituting the equation we have:
$$3n^2 - n+4\leq cn^2$$
Since I can choose $c$ to be, say, $5000$ and $n$ to be $1$, does that mean I have proven it is $O(n^2)$ because the righthand side will be larger?
On
According to Wikipedia:
Big O notation describes the limiting behaviour of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.
So, basically, Big O notation provides an upper bound on the value of the function as it approaches large values of the parameter. Mathematically, $f(n)=O(n^2)$ is the equivalent of saying that $$|f(n)|\leq M|n^2|$$ for $n>n_0$, choosing $M$ and $n_0$ as appropriate.
For example, $$f(n)=3n^2-n+4$$ $$f(n)=O(n^2)$$ Therefore we can say that $$|3n^2-n+4|\leq M|n^2|$$ If $M=8$ and $n_0=1$ respectively.
Why these values? Well, for $n>1$ $$|3n^2-n+4|\leq 3n^2 +|n|+4 \leq 3n^2+n^2+4n^2 = 8n^2$$ Thus $$f(n) \leq 8n^2$$ or $$f(n)=O(n^2)$$
For $n>1$ you have $$ 0<3n^2 - n + 4 \le 3n^2 +n^2 = 4n^2 $$