Notasi Big O

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

Definisi Big-O

Misalkan dipunyai barisan f:Nβ†’Rf: \mathbb{N} \to \mathbb{R}. Himpunan O(f)\mathcal{O}(f) didefinisikan sebagai berikut: O(f)=g:Nβ†’R:βˆƒc∈R>0:βˆƒn0∈N:βˆ€n>n0:0β‰€βˆ£g(n)βˆ£β‰€cβ‹…βˆ£f(n)∣.\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 ff maka O(f)\mathcal{O}(f) adalah sebuah himpunan barisan-barisan bilangan riil dengan syarat tertentu. Untuk memperjelas definisi di atas, perhatikan contoh berikut.

Misalkan f:Nβ†’Rf: \mathbb{N} \to \mathbb{R} dengan f(n)=n,βˆ€n∈Nf(n)=n, \forall n \in \mathbb{N}. Kita dapat buktikan bahwa g:Nβ†’Rg: \mathbb{N} \to \mathbb{R} dengan g(n)=2n,βˆ€n∈Ng(n)=2n, \forall n \in \mathbb{N} merupakan anggota dari himpunan O(f)\mathcal{O(f)}.

Last updated