Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Formal Definitions

For functions and with large input size , the three asymptotic notations are:

NotationMeaningCondition
is an asymptotic upper bound for all , some
is an asymptotic lower bound for all , some
is a tight bound and

So means for all . Small inputs do not matter, only the behaviour as .

The definitions sheet also gives the strict versions:

  • if for every as (grows strictly slower)
  • if for every as (grows strictly faster)

How to Prove a Bound

Method:

  • for , make the expression bigger: replace every lower-order term by the leading term, e.g. and for
  • for , make it smaller: drop the positive lower-order terms
  • state the constants and that make the inequality true
  • if both bounds use the same , conclude

Example 1

Show .

Upper bound: for ,

so , and .

Lower bound: for , so and . Hence .

Example 2

Show .

Since grows slower than , for :

So , , and .

Example 3: Log of a Factorial

Show , where means .

Upper bound: each of the factors is at most , so .

Lower bound: the largest factors are each at least , so

which is . Together this gives .

Growth When the Input Doubles

If the basic operation runs times, then

so doubling the input makes a quadratic algorithm about 4 times slower. The common growth classes, from slow to fast, are constant , logarithmic , linear , n-log-n , quadratic , cubic and exponential .