Analysis

Asymptotic Notations

• formal definition: $f(n) = O(g(n))$if there exists positive constants$c$and$n_0$such that $0 \le f(n) \le cg(n)$for all $n \ge n_0$.

• $\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) \le g(n)$	$n = O(n^2)$	$n^2 = O(n^2)$	$n^3 \neq O(n^2)$
$f(n) = \Omega(g(n))$	$f(n) \ge g(n)$	$n \neq \Omega(n^2)$	$n^2 = \Omega(n^2)$	$n^3 \neq \Omega(n^2)$
$f(n) = \Theta(g(n))$	$f(n) = g(n)$	$n \neq \Theta(n^2)$	$n^2 = \Theta(n^2)$	$n^3 \neq \Theta(n^2)$
$f(n) = o(g(n))$	$f(n) < g(n)$	$n = o(n^2)$	$n^2 \neq o(n^2)$	$n^3 \neq o(n^2)$
$f(n) = \omega(g(n))$	$f(n) > g(n)$	$n \neq \omega(n^2)$	$n^2 \neq \omega(n^2)$	$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(\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$\Phi (s)$for a certain state, and analyze the change of$\Phi$, from which we can derive the amortized cost