Algoritmizace – 4. cvičení

Složitost (O\mathcal{O})

Nechť f,f1,f2,g:N→R+f, f_1, f_2, g: \mathbb{N} \to \mathbb{R}^+. Dokažte nebo vyvraťte tato tvrzení:

  1. f∈O(g)  ⟹  1f∈O(1g)f \in \mathcal{O}(g) \implies \frac1f \in \mathcal{O}\left(\frac1g\right),
  2. f1∈O(g)∧f2∈O(g)  ⟹  f1+f2∈O(g)f_1 \in \mathcal{O}(g) \wedge f_2 \in \mathcal{O}(g) \implies f_1 + f_2 \in \mathcal{O}(g).