- zafixujeme výpočetní model = zafixujeme co je algoritmus = Turingův stroj (nejjednodušší možná varianta)
- jeden krok = jeden provedený krok turingova stroje
- zkoumáme nejhorší příklad
- logaritmy: lze převádět logaritmy
- sčítání: $\mathcal{O}(n^3) + \mathcal{O}(n) = \mathcal{O}(n^3)$
- mocniny: $2^{\mathcal{O}(n)}$ => $f(n) \leq 2^{c \cdot n}$
- $f \in \mathcal{O}(2^n) \implies f(n) \leq c \cdot 2^n = 2^{\log_2(c)} + 2^n = 2^{n \cdot \log_2(c)}$