The formal definition of the Big O notation is that if we have a function f(n) (for time and space of an algorithm) and another function g(x), and there are constants c and no such that c*g(n) > f(x) for all n > no, then f(n) = O(g(n)). But using this definition and the fact that a growing quadratic function always will surpass a linear function at some point, is it true that all O(n) functions are also O(n²)? Or better stated, is n = O(n²)?
Yes, all O(n) algorithms are O(n²), too. People are pretty sloppy with notation when it comes to Big-O. To be clear, I think it's best to conceptualize O(f) as returning a set of functions. Using set notation:
n ∈ O(n) ⊂ O(n²)