Asymptotic Notations — Short Note

Purpose

Describe algorithm growth for large $n$, abstracting constants/hardware, classifying efficiency (as in Q36/Q88).

Definitions

• $O(g(n))$: $∃c,n_0: 0≤f(n)≤c·g(n)$ $∀n≥n_0$ — at most $g$ (upper bound).
• $Ω(g(n))$: $∃c,n_0: 0≤c·g(n)≤f(n)$ — at least $g$ (lower bound).
• $Θ(g(n))$: $∃c_1,c_2,n_0: c_1g≤f≤c_2g$ — tight bound ($O∩Ω$).
• $o(g)$: $∀c>0$ eventually $f<c·g$ — strict upper ($f/g→0$).
• $ω(g)$: strict lower ($f/g→∞$).

Examples

• $3n^2+2n+1 = Θ(n^2)=O(n^2)=O(n^3)=Ω(n^2)=Ω(n)$.
• $n\log n = o(n^2)$, $2^n = ω(n^{100})$.

Hierarchy

$O(1)⊂O(\log n)⊂O(n)⊂O(n\log n)⊂O(n^2)⊂O(2^n)⊂O(n!)$ — helps choose algorithm (e.g., merge $n\log n$ vs insertion $n^2$).

Properties

Transitivity, reflexivity, symmetry for $Θ$, transpose $f=O(g)⇔g=Ω(f)$, sum rule $f_1+f_2=O(max(g_1,g_2))$.

Use: Analyze worst/best/average cases; e.g., linear search worst $Θ(n)$, binary $Θ(\log n)$, quicksort avg $Θ(n\log n)$.