Comment on page

Analysis

Asymptotic Notations
formal definition: f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n))
if there exists positive constantsccc
andn0n_0n0​
such that 0≤f(n)≤cg(n)0 \le f(n) \le cg(n)0≤f(n)≤cg(n)
for all n≥n0n \ge n_0n≥n0​
. 
​lim⁡n→∞f(n)g(n)≤constant\lim_{n\to\infty} \frac{f(n)}{g(n)} \le constantlimn→∞​g(n)f(n)​≤constant
 
notation
(literal) meaning
example 1
example 2
example 3
​f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n))
 
​f(n)≤g(n)f(n) \le g(n)f(n)≤g(n)
​
​n=O(n2)n = O(n^2)n=O(n2)
​
​n2=O(n2)n^2 = O(n^2)n2=O(n2)
​
​n3≠O(n2)n^3 \neq O(n^2)n3=O(n2)
​
​f(n)=Ω(g(n))f(n) = \Omega(g(n))f(n)=Ω(g(n))
 
​f(n)≥g(n)f(n) \ge g(n)f(n)≥g(n)
​
​n≠Ω(n2)n \neq \Omega(n^2)n=Ω(n2)
​
​n2=Ω(n2)n^2 = \Omega(n^2)n2=Ω(n2)
​
​n3≠Ω(n2)n^3 \neq \Omega(n^2)n3=Ω(n2)
​
​f(n)=Θ(g(n))f(n) = \Theta(g(n))f(n)=Θ(g(n))
 
​f(n)=g(n)f(n) = g(n)f(n)=g(n)
​
​n≠Θ(n2)n \neq \Theta(n^2)n=Θ(n2)
​
​n2=Θ(n2)n^2 = \Theta(n^2)n2=Θ(n2)
​
​n3≠Θ(n2)n^3 \neq \Theta(n^2)n3=Θ(n2)
​
​f(n)=o(g(n))f(n) = o(g(n))f(n)=o(g(n))
 
​f(n)<g(n)f(n) < g(n)f(n)<g(n)
​
​n=o(n2)n = o(n^2)n=o(n2)
​
​n2≠o(n2)n^2 \neq o(n^2)n2=o(n2)
​
​n3≠o(n2)n^3 \neq o(n^2)n3=o(n2)
​
​f(n)=ω(g(n))f(n) = \omega(g(n))f(n)=ω(g(n))
 
​f(n)>g(n)f(n) > g(n)f(n)>g(n)
​
​n≠ω(n2)n \neq \omega(n^2)n=ω(n2)
​
​n2≠ω(n2)n^2 \neq \omega(n^2)n2=ω(n2)
​
​n3=ω(n2)n^3 = \omega(n^2)n3=ω(n2)
​
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})O(nf(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)Φ(s)
for a certain state, and analyze the change ofΦ\PhiΦ
, from which we can derive the amortized cost

Sorting

Complexity Classes (P, NP)

Last modified 2yr ago

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