Computer Science Mojo

~ David's Notes on coding, software and computer science




Post

How to classify and compare algorithm asymptotic runtimes

Category: Algorithm     Tag: Algorithm   Discrete Math   Runtime  
By: David     On: Fri 11 September 2015      Pageviews: 28

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 ) $$