Büyük O gösterimi, bir fonksiyonun başka bir fonksiyona göre asimptotik üst sınırını belirtir. Bilgisayar bilimlerinde, girdi büyüdükçe bir algoritmanın çalışma süresi veya bellek gereksiniminin nasıl arttığını özetlemek için kullanılır. n çoğunlukla girdi boyutunu gösterir; sonuç, belirli bir bilgisayarda ölçülen saniye sayısı değildir. Sabit katsayılar ve yeterince küçük girdiler için görülen farklar bu büyüme ölçüsünde belirleyici sayılmaz. [1][2]
Matematiksel tanım
f(n)=O(g(n)) yazımı, yeterince büyük n değerlerinde f(n)’in g(n)’in sabit bir katıyla üstten sınırlanması anlamına gelir. Bunun için pozitif c ve n₀ sabitleri bulunmalı; her n≥n₀ için f(n)≤c·g(n) koşulu sağlanmalıdır. Örneğin 3n+8, O(n)’dir: sabit katsayı ve toplamsal terim, büyük n’de doğrusal üst sınırı değiştirmez. Büyük O tek başına en sıkı sınırı ifade etmez. Doğrusal büyüyen bir fonksiyon aynı zamanda O(n²) koşulunu da karşılar; fakat O(n) daha açıklayıcı ve sıkı üst sınırdır. [1][2]
Algoritmaları çözümleme
Algoritmanın işlem sayısı, girdi boyutunun fonksiyonu olarak incelenebilir. Tüm öğeleri bir kez dolaşmak çoğu zaman doğrusal büyüme, her öğe çifti için karşılaştırma yapmak ise karesel büyüme örneği verir. Sıralı bir dizide arama aralığını her adımda yarıya indiren ikili arama logaritmik büyümeye örnektir. Bu sınıflar, büyük girdilerde algoritmaları makineden bağımsız biçimde karşılaştırmayı kolaylaştırır; gerçek çalışma süresi yine uygulama, donanım ve sabit maliyetlerden etkilenir. Ayrıca büyük O, kendiliğinden “en kötü durum” demek değildir. Çözümlemede kullanılan fonksiyonun en kötü, ortalama veya en iyi durumu temsil edip etmediği ayrıca belirtilmelidir. Bu nedenle sonuç hem girdi ölçüsünü hem de incelenen kaynak ve durumu açıklamalıdır. [1][2]