Complexity Classes
The Computational Zoo is far more subtle and complex than I thought it was.
It contains P, NP (+complete), EXP, NP-hard, CO-NP (+complete), PSPACE, BPP, BQP, EXPSPACE, 2-EXP, halting problem, decidable, etc!
Big Oh Notation
Big-Oh ( \(O\) ) gives an upper bound on how an algorithm’s resource consumption grows with input size \(n\).
Definition. A function \(f(n)\) is \(O(g(n))\) iff \[ \exists\,c>0,\; \exists\,n_0\ge 1 \; \text{s.t.}\; 0\le f(n)\le c\,g(n)\quad\forall\,n\ge n_0 . \]
explained!