Notasi Big-O

Dalam bagian ini, akan diperkenalkan konsep Big-O dengan pendekatan barisan bilangan riil.

Definisi Big-O

Misalkan dipunyai barisan $f: \mathbb{N} \to \mathbb{R}$. Himpunan $\mathcal{O}(f)$ didefinisikan sebagai berikut: $\mathcal{O}(f) = { g: \mathbb{N} \to \mathbb{R}: \exists c \in \mathbb{R}_{>0}: \exists n_0 \in \mathbb{N}: \forall n > n_0: 0 \le | {g(n)}| \le c \cdot | {f(n)}|}.$

Dari definisi di atas terlihat bahwa jika kita punya fungsi $f$ maka $\mathcal{O}(f)$ adalah sebuah himpunan barisan-barisan bilangan riil dengan syarat tertentu. Untuk memperjelas definisi di atas, perhatikan contoh berikut.

Misalkan $f: \mathbb{N} \to \mathbb{R}$ dengan $f(n)=n, \forall n \in \mathbb{N}$. Kita dapat buktikan bahwa $g: \mathbb{N} \to \mathbb{R}$ dengan $g(n)=2n, \forall n \in \mathbb{N}$ merupakan anggota dari himpunan $\mathcal{O(f)}$.