Asymptotic Notations & Properties

Definitions (as in Q36)

• $O(g)$ upper: $\exists c,n_0: 0\le f(n)\le c g(n)$ $\forall n\ge n_0$.
• $\Omega(g)$ lower: $\exists c,n_0: 0\le c g(n)\le f(n)$.
• $\Theta(g)$ tight: $c_1 g(n)\le f(n)\le c_2 g(n)$ → $O \cap \Omega$.
• $o(g)$ strict upper: $\forall c>0$ $f(n)<c g(n)$ eventually ($f/g\to0$).
• $\omega(g)$ strict lower ($f/g\to\infty$).

Properties

1. Transitivity: $f=O(g), g=O(h)\Rightarrow f=O(h)$ (similar for $\Omega,\Theta$).
2. Reflexivity: $f=\Theta(f)$.
3. Symmetry: $f=\Theta(g)\iff g=\Theta(f)$; transpose symmetry $f=O(g)\iff g=\Omega(f)$.
4. Additivity/Max rule: If $f_1=O(g_1), f_2=O(g_2)$ then $f_1+f_2=O(\max(g_1,g_2))$. Hence polynomial $a_k n^k+\dots=O(n^k)$.
5. Scaling: $c f(n)=\Theta(f(n))$ for constant $c>0$; lower-order terms absorbed.
6. Ordering: $O(1)\subset O(\log n)\subset O(n)\subset O(n\log n)\subset O(n^2)\subset O(n^3)\subset O(2^n)\subset O(n!)$.
7. Polynomial gap: $n^{a}=o(n^{b})$ if $a<b$; any poly is $o(2^n)$.
8. Master/recurrence use: notations hide constants allowing comparison Unabhängig von Hardware.

Example Hierarchy

• Linear search worst $\Theta(n)$, binary $\Theta(\log n)$, merge $\Theta(n\log n)$, matrix mult naive $\Theta(n^3)$, Strassen $\Theta(n^{2.81})$, TSP brute $\Theta(n!)$.

Pitfalls

• $O$ is not tight — use $\Theta$ when both upper and lower known.
• Not all functions comparable ($n^{\sin n}$ incomparable).
• Amortized vs worst-case: $O$ still worst over sequence.