Notasi O besar

Contoh notasi O besar: $f(x)\in O(g(x))$ karena ada $M>0$ (yakni, $M=1$) dan $x_0$ (yakni, $x_0=5$) sehingga $f(x)\le Mg(x)$ dengan $x\ge x_0$.

Notasi O besar, atau notasi Bachmann–Landau atau notasi asimtotik merupakan notasi matematika yang menjelaskan perilaku pada batas suatu fungsi ketika argumen cenderung menuju ke nilai yang khusus atau takhingga. Notasi O besar merupakan anggota dari keluarga notasi yang ditemukan oleh Paul Bachmann, Edmund Landau, dan matematikawan lain. Notasi O yang dipilih Bachmann mengartikan Ordnung, yang berarti orde aproksimasi.

Notasi O besar dikaitkan dengan notasi yang berbeda. Ada yang menggunakan Templat:Math, dan Templat:Math, yang dipakai untuk menjelaskan jenis batas lain pada laju pertumbuhan asimtotik.

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))$ ketika $x\to \mathrm{\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_0$ sedemikian sehingga

$|f(x)|\le Mg(x)$, untuk semua $x\ge 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))$ ketika $x\to a$.

jika dan hanya jika terdapat bilangan positif $\delta$ dan $M$ sedemikian sehingga

$|f(x)|\le Mg(x)$ ketika $0<|x-a|<\delta$.

Contoh

Dalam penggunaannya, notasi $O$ dapat menyederhanakan fungsi $f$. Sebagai contoh, misalkan $f(x)=6x^4-2x^3+5$, fungsi $f$ dapat ditulis sebagai

$f(x)=O(x^4)$.

Bacaan lebih lanjut

• Templat:Cite book
• Templat:Cite book
• Templat:Cite book
• Templat:Cite book
• Templat:Cite conference
• Templat:Cite web
• Templat:Cite web
• Templat:Cite web
• Templat:Cite web
• Templat:Cite web

Pranala luar

• Growth of sequences — OEIS (Online Encyclopedia of Integer Sequences) Wiki
• Landau Symbols
• Big-O Notation – What is it good for
• Big O Notation explained in plain english
• An example of Big O in accuracy of central divided difference scheme for first derivative Templat:Webarchive
• A Gentle Introduction to Algorithm Complexity Analysis