Notasi O besar

Notasi O besar (big-O notation) atau notasi Bachmann–Landau atau notasi asimtotik adalah notasi matematika yang digunakan terutama pada bidang ilmu komputer (computer science). Notasi ini digunakan untuk menyatakan keefektifan sebuah algoritme. Notasi ini bekerja dengan cara memperhitungkan input yang diberikan oleh user.

Definisi Formal

Misalkan f adalah fungsi bernilai riil ataupun kompleks dan g adalah fungsi bernilai riil, dan keduanya terdefinisi pada sebuah subhimpunan tak hingga dari bilangan riil positif, sedemikian sehingga g(x) bernilai positif untuk semua nilai x yang cukup besar, maka

$f(x)=O(g(x)){\text{ as }}x\to \infty$

jika dan hanya jika untuk semua nilai x yang cukup besar, nilai absolut dari f(x) tidak melebihi g(x) dikali dengan sebuah konstanta positif. Dengan kata lain, f(x) = O(g(x)) jika dan hanya jika terdapat sebuah bilangan riil positif M dan sebuah bilangan riil x₀ sedemikian sehingga

$|f(x)|\leq \;Mg(x){\text{ for all }}x\geq x_{0}.$

Dalam banyak kasus, kita hanya tertarik dengan laju pertumbuhan variabel x yang menuju tak hingga sehingga pernyataan tersebut tidak disebutkan lagi, dan hanya ditulis sebagai

$f(x)=O(g(x)).$

Notasi ini juga dapat mendeskripsikan perilaku fungsi f di dekat sebuah bilangan riil a (biasanya a = 0), maka dapat dikatakan

$f(x)=O(g(x)){\text{ as }}x\to a$

jika dan hanya jika terdapat bilangan positif δ dan M sedemikian sehingga

$|f(x)|\leq \;Mg(x){\text{ when }}0<|x-a|<\delta .$

Contoh

Dalam penggunaannya, notasi O dapat menyederhanakan fungsi f. Sebagai contoh, misalkan f(x) = 6x⁴ − 2x³ + 5, fungsi f dapat ditulis sebagai

$f(x)=O(x^{4})$