Big O Notation - Matters of Notation - Equals Sign

Equals Sign

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(x2) is true but O(x2) = O(x) is not. Knuth describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like n = n2 from the identities n = O(n2) and n2 = O(n2)." For these reasons, it would be more precise to use set notation and write f(x) ∈ O(g(x)), thinking of O(g(x)) as the class of all functions h(x) such that |h(x)| ≤ C|g(x)| for some constant C. However, the use of the equals sign is customary. Knuth pointed out that "mathematicians customarily use the = sign as they use the word 'is' in English: Aristotle is a man, but a man isn't necessarily Aristotle."

Read more about this topic:  Big O Notation, Matters of Notation

Other articles related to "equals sign, equal":

Equals Sign - Incorrect Usage
... The equals sign can be used incorrectly within a mathematical argument, if used in a manner that connects steps of math in a non-standard way, rather than to show equality ...
Assignment (computer Science) - Assignment Versus Equality
... A notorious example for a bad idea was the choice of the equal sign to denote assignment ... are on unequal footing The left operand (a variable) is to be made equal to the right operand (an expression) ... In some languages, such as BASIC, a single equals sign ("=") is used for both the assignment operator and the equality relational operator, with context determining which is meant ...

Famous quotes containing the words sign and/or equals:

    It is a sign of our times, conspicuous to the coarsest observer, that many intelligent and religious persons withdraw themselves from the common labors and competitions of the market and the caucus, and betake themselves to a certain solitary and critical way of living, from which no solid fruit has yet appeared to justify their separation.
    Ralph Waldo Emerson (1803–1882)

    Inferiors revolt in order that they may be equal, and equals that they may be superior. Such is the state of mind which creates revolutions.
    Aristotle (384–322 B.C.)