En iyi, ortalama, en kötü durum karmaşıklığı

Bazı durumlarda en iyi, ortalama, en kötü durum karmaşıklığı gözönüne almak gerekir
  En kötü, O(N) veya o(N):  veya > asıl fonksiyon   *
  Genel, Θ(N):  asıl fonksiyon                                   *
  En iyi, Ω(N):  asıl fonksiyon                                  *

Örnek: Liste sıralarken eğer liste zaten sıralıya yakınsa yapılacak iş azdır.
En kötü durum muhtemel bütün girdiler için bir sınır çizer ve genelde ortalamadan daha kolay bulunur

Ω Notasyonu- Asimtotik Alt Limit

 O notasyonun tam tersidir.
 Her durumda T(N) Ωc f(n) ve N Ω n0 koşullarını      sağlayan  pozitif, sabit c ve n0 değerleri bulunabiliyorsa T(N)=Ω(f(n))  ifadesi doğrudur.

 f(n), T(N)’in asimtotik alt limiti olarak
adlandırılır.


Ω Notasyonu Örnek 1

7n2+3n+5 = O(n4)
7n2+3n+5 = O(n3)
7n2+3n+5 = O(n2)
7n2+3n+5 = Ω(n2)
7n2+3n+5 = Ω(n)
7n2+3n+5 = Ω(1)


Algoritma 1



   int  Sum (int N)
   {
     int i, PartialSum;
     PartialSum=0;
   for(i=1  ;i<=N ; i++)
      PartialSum+=i*i*i;
   return PartialSum;
   }

Çalışma zamanı 6N+4=O(N)

Performans her şey demek değildir!

Bazen aşağıdaki iki durum birbiriyle çelişebilir:
Anlama, yazma ve hata ayıklama kolaylığı
Zaman ve yerin verimli kullanılmasıEfficient use of time and space
Bu nedenle maksimum performans her zaman tercih edilmeyebilir
Ancak yine de en uygun algoritmayı kullanmak mümkün olmasa da farklı yöntemleri karşılaştırmak yararlıdır.