A friend of mine, who is currently enrolled in the Algorithms course over at Coursera reached out to me with the following problem:

Assume two (positive) nondecreasing functions and . If , is it also true that ?

My friend felt unable to apply his understanding of
big-O notation
to this question.
In fact, he felt tripped up by the signs in the above expression.
I remembered being similarly at a loss a decade earlier doing my first Algorithms course at my alma mater,
BITS Pilani,
and I now realize that my confusion was at least partly due to bad notation.
Computer Science-folks (as opposed to mathematicians),
when teaching complexity, do not emphasize
*at all*
that big-O actually refers to a
**class**, or a **family** of functions,
rather than a single one:

is the set of all functions whose absolute value (asymptotically) grows no faster than , by up to a constant factor.

Armed with the above informal definition, we (the mathematically trained) immediately see an abuse of notation in the above problem with:

and realize that the expression would be better written as

The **belongs-to** symbol () is more appropriate
than the **equality** symbol () since the left hand side
is a single function, while the right hand side is a family of functions.
In other words, we are making *a statement about set membership*.
Unfortunately, this abuse of notation is widespread in Computer Science literature.
Newcomers, as always, bear the brunt.

Before answering the original problem my friend posed, consider the more general problem:

Given two functions and , if , is it also true that ?

The answer is **no**, since and is a counterexample.
Since grows no faster than , we get that .
But *does* grow faster than ,
and so .

The nature of the counterexample however indicates to us that if we imposed the restriction that the functions were positive and non-decreasing, things might be different. In fact, if , , and , then

In other words, **yes**,
if and are positive, and
, then
.