Wikipedia says:
The statement "f(x) is O(g(x))" as defined above is usually written as
f(x) = O(g(x)). Some consider this to be an abuse of notation, since
the use of the equals sign could be misleading as it suggests a
symmetry that this statement does not have. As de Bruijn says, O(x) =
O(x^2) is true but O(x^2) = O(x) is not
I understand the formal definition but not what de Bruin says. Im puzzeled by trying to understand what O(x) = O(x^2) or even O(x) is O(x^2) really means.
Intuitively I would read it as "The class of functions with complexity x is the same as the class of functions with complexity x^2". But that does not make sense.
The wikipedia talk page does not help much either.
Intuitively I would read it as "The class of functions with complexity x is the same as the class of functions with complexity x^2". But that does not make sense.
Yes, and that is why people don't like the notation with the equals sign.
It should read as "The class of functions with complexity x is included in the class of functions with complexity x^2" or "A function with a linear upper bound for complexity is also a function with a quadratic upper complexity bound" (where of course the quadratic bound is not very tight).
In math, '=' is usually expected represent "equality", and should be an equivalence relation. This means it should be reflexive, symmetric and transitive.
As de Bruijn says, O(x) = O(x^2) is true but O(x^2) = O(x) is not
means the relation is not symmetric.
