Notasi O besar

Contoh notasi O besar: ${\color {red}f(x)}\in O{\color {blue}(g(x))}$ karena ada $M>0$ (yakni, $M=1$) dan $x_{0}$ (yakni, $x_{0}=5$) sehingga ${\color {red}f(x)}\leq {\color {blue}Mg(x)}$ dengan $x\geq 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 o, Ω, ω, dan Θ, 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 \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)|\leq \;Mg(x)$, untuk semua $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))$ ketika $x\to a$.

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

$|f(x)|\leq \;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

• Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. 
• Knuth, Donald (1997). "1.2.11: Asymptotic Representations". Fundamental Algorithms. The Art of Computer Programming. 1 (edisi ke-3rd). Addison-Wesley. ISBN 978-0-201-89683-1. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "3.1: Asymptotic notation". Introduction to Algorithms (edisi ke-2nd). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. 
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. hlm. 226–228. ISBN 978-0-534-94728-6. 
• Avigad, Jeremy; Donnelly, Kevin (2004). Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. doi:10.1007/978-3-540-25984-8_27. 
• Black, Paul E. (11 March 2005). Black, Paul E., ed. "big-O notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
• Black, Paul E. (17 December 2004). Black, Paul E., ed. "little-o notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
• Black, Paul E. (17 December 2004). Black, Paul E., ed. "Ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
• Black, Paul E. (17 December 2004). Black, Paul E., ed. "ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 
• Black, Paul E. (17 December 2004). Black, Paul E., ed. "Θ". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Diakses tanggal December 16, 2006. 

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 Diarsipkan 2018-10-07 di Wayback Machine.
• A Gentle Introduction to Algorithm Complexity Analysis