3 ms·
But big-O is not an equivalence relation on functions, because it isn't an equivalence relation. A big-O relationship is not symmetric: if f(x) = x² and g(x) =
by thaumasiotes 4y ago
But big-O is not an equivalence relation on functions, because it isn't an equivalence relation. A big-O relationship is not symmetric: if f(x) = x² and g(x) = x³, you can see immediately that f(x) = O( g(x) ), but it is not true that g(x) = O( f(x) )
Big-O is a statement about the limit of a function as the input goes to infinity. f(x) = O( g(x) ) is the statement that the limit (f/g)(x) exists as x goes to infinity. f(x) = o( g(x) ) is the stronger statement that the same limit exists and is equal to zero.