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²)?
Are all O(n) algorithms O(n²) too?
Viewed 188
2 Answers
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²)
Certainly. Apply your definition with f(n)=n, g(n)=n^2, c=1, and n0=1, to see that f is O(n^2). All you need to notice is that when n > n0 = 1, we have
n = 1*n = n0*n < n*n = n^2
A similar argument shows that every O(n) function is O(n^2).
In essence, big O is about providing an asymptotic upper bound. There is no requirement that this upper bound be sharp; that is what big Theta is for.
Related