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:
| Notation | Meaning | Condition |
|---|---|---|
| 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 .