Analysis of Algorithm

Big 0

• We say $f(n) = O(g(n))$ iff there exists constants $c$ and $n_0$ such that $f(n)\leq c \leq g(n)$ for all $n \geq n_0$
• {n/4, 2n + 3, ..., n/100000, log(n) + 100} ∈ O(n) (equal or less)
• Upper bound

Omega Ω

• f(n) = Ω(g(n)) iff there exists positive constants c and n0 such that 0 <= c.g(n) <= f(n) for all n >= n0
• {n/4, n^2,..., n^n} ∈ Ω(n)
• useful when we have lower bound

Theta θ

• f(n)=θ(g(n)) iff there exist constants c1, c2 (where c1>0 and c2>0) and n0 (where n0>=0) such that c1g(n) <= f(n) <= c2g(n) for all n>=n0
• Exact bound