Asymptotic Notations

  • formal definition: f(n)=O(g(n))f(n) = O(g(n))if there exists positive constantsccandn0n_0such 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


(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


  • 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


  • 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

Last updated