Comment on page

# 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