Comment on page

Analysis

Asymptotic Notations

  • formal definition:
    f(n)=O(g(n))f(n) = O(g(n))
    if there exists positive constants
    cc
    and
    n0n_0
    such that
    0f(n)cg(n)0 \le f(n) \le cg(n)
    for all
    nn0n \ge n_0
    .
  • limnf(n)g(n)constant\lim_{n\to\infty} \frac{f(n)}{g(n)} \le constant
notation
(literal) meaning
example 1
example 2
example 3
f(n)=O(g(n))f(n) = O(g(n))
f(n)g(n)f(n) \le g(n)
n=O(n2)n = O(n^2)
n2=O(n2)n^2 = O(n^2)
n3O(n2)n^3 \neq O(n^2)
f(n)=Ω(g(n))f(n) = \Omega(g(n))
f(n)g(n)f(n) \ge g(n)
nΩ(n2)n \neq \Omega(n^2)
n2=Ω(n2)n^2 = \Omega(n^2)
n3Ω(n2)n^3 \neq \Omega(n^2)
f(n)=Θ(g(n))f(n) = \Theta(g(n))
f(n)=g(n)f(n) = g(n)
nΘ(n2)n \neq \Theta(n^2)
n2=Θ(n2)n^2 = \Theta(n^2)
n3Θ(n2)n^3 \neq \Theta(n^2)
f(n)=o(g(n))f(n) = o(g(n))
f(n)<g(n)f(n) < g(n)
n=o(n2)n = o(n^2)
n2o(n2)n^2 \neq o(n^2)
n3o(n2)n^3 \neq o(n^2)
f(n)=ω(g(n))f(n) = \omega(g(n))
f(n)>g(n)f(n) > g(n)
nω(n2)n \neq \omega(n^2)
n2ω(n2)n^2 \neq \omega(n^2)
n3=ω(n2)n^3 = \omega(n^2)
more reference: Orders of common functions

Randomized Algorithms and Average-case Analysis

Examples

  • the hiring problem: in average O(log(n)) instead of O(n)
  • quicksort: the cost is O(n log(n)) on average
  • hash table: expected O(1)
  • Rabin-Karp: sub-string matching

Amortized Analysis

Though the algorithm is deterministic, the cost of each step may be different

Examples

  • Binary Counter and Piggy Bank
    • pay only when a bit changes from 0 to 1
  • Hash Table
    • load factor better to be 1/2
    • need to resize when full
      • worst case cost: O(n)
      • amortized to O(1)
  • Union-find with path-compression: O(log* n) per union or per find
  • Weight balanced tree with rebuilding
    • O(log n) cost per insertion
      • O(1) cost for rebalance per insertion
      • O(log n) cost for insertion itself

Three ways for amortized analysis

  • Direct: count the total cost from an empty state all the way to the n-th operation O(f(n))
    • then the total cost of each operation is
      O(f(n)n)O(\frac{f(n)}{n})
  • Piggy bank: pay O(k) “dollars” per operation
    • show that even though some of the operations are more expensive, the total cost of all n elements are no more than O(nk)
  • Potential function: design a potential function
    Φ(s)\Phi (s)
    for a certain state, and analyze the change of
    Φ\Phi
    , from which we can derive the amortized cost