Algoritmizace – 3. cvičení

Složitost (\mathcal{O})

Definice

Nechť f, g: \mathbb{N} \to \mathbb{R}^+.

• f \in \mathcal{O}(g) \iff \exists c > 0, \exists n_0: \forall n > n_0: f(n) \leq c \cdot g(n).
• f \in \mathcal{\Omega}(g) \iff \exists c > 0, \exists n_0: \forall n > n_0: f(n) \geq c \cdot g(n).
• f \in \mathcal{\Theta}(g) \iff f \in \mathcal{O}(g) \wedge f \in \mathcal{\Omega}(g).

Úlohy

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

1. n^2 \in \mathcal{O}(n^3),
2. n^3 \in \mathcal{O}(n^2)
3. f \in \mathcal{O}(g) \implies g \in \mathcal{O}(f),
4. f \in \mathcal{O}(g) \implies g \in \mathcal{\Omega}(f),
5. f \in \mathcal{O}(g) \vee g \in \mathcal{O}(f).

Vzorová řešení a moje poznámky (ne úplně vzorové řešení, ale všechny hlavní myšlenky by tam měly být).