(Taking a Algorithms course now, so I might get it wrong, if so, RIP to my finals in a few weeks)

I think O notation represents the upper bound, so a complexity of N can also be said as O(N^2) or O(N^3), but that isn't particularly useful.

In other words, if f(x)/g(x) < inf when x->inf, then f(x) = O(g(x)).

Then there's omega-notation (lower bound, f(x)/g(x) > 0) and theta-notation (both lower and upper bound, 0 < f(x)/g(x) < inf).

Yeah this is right. Big O can be thought of as meaning “eventually always smaller than a multiple of” so f(n) = O(g(n)) as n -> inf means that there is some N (the “eventually” part) and M (the “multiple of” part) such that, for every n > N, |f(n)| < M g(n).