Big O notation - Matters of notation

Big O notation - Wikipedia, the free encyclopedia:
The statement "f(x) is O(g(x))" as defined above is often written as f(x) = O(g(x)). This is a slight abuse of notation: we are not really asserting the equality of two functions. Here is a bad example:

O(x) = O(x²) but O(x²) ≠ O(x)

By this reason, some authors prefer a set notation and write f ∈ O(g), thinking of O(g) as the set of all functions dominated by g.
Furthermore, an "equation" of the form
f(x) = h(x) + O(g(x))
is to be understood as "the difference of f(x) and h(x) is O(g(x))".

In casual use, O is commonly used where Θ is meant, i.e., a tight estimate is implied. For example, one might say "heapsort is O(n log n) in average case" when the intended meaning was "heapsort is Θ(n log n) in average case". Both statements are true, but the latter is a stronger claim.

**) Here is a hint (and mnemonics) why Landau selected these Greek letters: "omicron" is "o-micron", i.e., "o-small", whereas "o-mega" is "o-BIG".

Prime Number

from MathWorld:
Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate" (Havil 2003, p. 163).

In a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171).