How to classify and compare algorithm asymptotic runtimes
Asymptotic runtimes can be classified to help with comparison and understanding. There are also some tricky examples that can't be classified at first sight, but will require simple mathematical transformations.
Note
- Using constants a, b, c
- Using variables n, x, y
- log without subscript is for simplicity, assume \(log_2\) if a value is necessary (the base doesn't matter because \( log_b(x) = {log_a(x) \over log_a(b)} \))
Runtime Table
| Runtime | Type | Short | Function ƒ(n) |
|---|---|---|---|
| Shortest | Constant | a | \(a\) |
| Logarithmic | Log | \(log (n)\) | |
| Polylogarithmic | Poly Log | \(log^a (n)\) | |
| <1 Polynomial | Small Poly | \(n^a \quad (a<1)\) | |
| Linear | n | \(n\) | |
| Linearithmic | n log (n) | \(n log (n)\) | |
| >1 Polynomial | Big Poly | \(n^a \quad (a>1)\) | |
| Exponential | Expo | \(a^n \quad (a>1)\) | |
| Factorial | Fact | \(n!\) | |
| Longest | Power n | n n | \(n^n\) |
log transformations:
- \( a^{log_a(x)} = x \)
- \( log_a(a^x) = x \)
- \( log_b(x) = {log_a(x) \over log_a(b)} \)
- \(log(xy) = log(x) + log(y) \)
- \( log (x^y) = y log (x) \)
- \( x^{log (y)} = y^{log (x)} \)
- log preserves inequality: You can log both sides of an inequality as long as both sides are positive
Tricky comparison examples that require transformation:
1. Transformations:
\( a^{log_a(x)} = x \) $$ 2^{log(n)} = n $$ summation \( \sum \) $$ \sum_1^n n^2 = n^3 $$
2. Divide to a known runtime:
\(n \over log(n)\) vs <1 Polynomial: Divide by \( n^{1 \over 2}\) $$ {n \over log(n)} \quad vs \quad n^{1 \over 2}$$ $${n^{1 \over 2} \over log(n)} \quad > \quad 1$$
3. log both sides:
Especially when there is a \( 2^x \) \(n^{log(n)}\) vs Exponential : $$ n^{log(n)} \quad vs \quad 2^n $$ $$ log(n^{log(n)}) \quad vs \quad log(2^n)$$ $$ log^2 (n) \quad < \quad n $$ \(n!\) vs \(2^{n^2}\) : $$ n! \quad vs \quad 2^{n^2} $$$$ log(n!) \quad vs \quad log(2^{n^2}) $$$$\text{use } n^n \text{ for } n!$$$$ log(n^n) \quad vs \quad n^2 $$$$ n log(n) \quad < \quad n^2 $$ \(n(log n)^{10}\) vs > 1 Polynomial: $$ n(log n)^{10} \quad vs \quad n^{1.1} $$$$ log n^{10} \quad vs \quad n^{0.1} $$$$ 10 log( log n) \quad < \quad 0.1 log( n ) $$