Well I found the relevant part of the book. Indeed the excerpt comes from the chapter introducing big-O notation and relatives.
The formal definition of the big-O is that the function in question does not grow asymptotically faster than the comparison function. It does not say anything about whether the function grows asymptotically slower, so:
f(n) = n
is in O(n)
, O(n^2)
and also O(e^n)
because n
does not grow asymptotically faster than any of these. But n
is not in O(1)
.
Any function in O(n)
is also in O(n^2)
and O(e^n)
.
If you want to describe the tight asymptotic bound, you would use the big-Θ notation, which is introduced just before the big-O notation in the book. f(n) ∊ Θ(g(n))
means that f(n)
does not grow asymptotically faster than g(n)
and the other way around. So f(n) ∊ Θ(g(n))
is equivalent to f(n) ∊ O(g(n))
and g(n) ∊ O(f(n))
.
So f(n) = n
is in Θ(n)
but not in Θ(n^2)
or Θ(e^n)
or Θ(1)
.
Another example: f(n) = n^2 + 2
is in O(n^3)
but not in Θ(n^3)
, it is in Θ(n^2)
.
You need to think of O(...)
as a set (which is why the set theoretic "element-of"-symbol is used). O(g(n))
is the set of all functions that do not grow asymptotically faster than g(n)
, while Θ(g(n))
is the set of functions that neither grow asymptotically faster nor slower than g(n)
. So a logical consequence is that Θ(g(n))
is a subset of O(g(n))
.
Often =
is used instead of the ∊
symbol, which really is misleading. It is pure notation and does not share any properties with the actual =
. For example 1 = O(1)
and 2 = O(1)
, but not 1 = O(1) = 2
. It would be better to avoid using =
for the big-O notation. Nonetheless you will later see that the =
notation is useful, for example if you want to express the complexity of rest terms, for example: f(n) = 2*n^3 + 1/2*n - sqrt(n) + 3 = 2*n^3 + O(n)
, meaning that asymptotically the function behaves like 2*n^3
and the neglected part does asymptotically not grow faster than n
.
All of this is kind of against the typically usage of big-O notation. You often find the time/memory complexity of an algorithm defined by it, when really it should be defined by big-Θ notation. For example if you have an algorithm in O(n^2)
and one in O(n)
, then the first one could actually still be asymptotically faster, because it might also be in Θ(1)
. The reason for this may sometimes be that a tight Θ-bound does not exist or is not known for given algorithm, so at least the big-O gives you a guarantee that things won't take longer than the given bound. By convention you always try to give the lowest known big-O bound, while this is not formally necessary.