Big-Theta (Θ) notasyonu, bir algoritmanın çalışma süresini hem üst hem de alt sınırlar açısından ifade eder. Bu notasyon, bir algoritmanın çalışma süresinin girdi boyutu n'in bir fonksiyonu olarak belirli bir aralıkta olduğunu gösterir.

Örneğin, bir algoritmanın çalışma süresi Θ(n) olarak ifade edilirse, bu, girdi boyutu n'e bağlı olarak algoritmanın çalışma süresinin bir sabit çarpanla n ve başka bir sabit çarpanla n arasında olduğunu belirtir. Yani, bu algoritmanın çalışma süresi girdi boyutuyla doğru orantılıdır ve hem en kötü durumda (O(n)) hem de en iyi durumda (Ω(n)) bu doğru orantılılık korunur.

Bir algoritmanın çalışma süresi Θ(n^2) olarak ifade edilirse, bu, girdi boyutu n'in karesine bağlı olarak algoritmanın çalışma süresinin bir sabit çarpanla n^2 ve başka bir sabit çarpanla n^2 arasında olduğunu belirtir. Bu, algoritmanın çalışma süresinin girdi boyutunun karesiyle orantılı olduğunu ve hem en kötü durumda (O(n^2)) hem de en iyi durumda (Ω(n^2)) bu orantıyı koruduğunu gösterir.

Big-Theta notasyonu, bir algoritmanın karmaşıklığını daha hassas bir şekilde ifade etmeye yardımcı olur, çünkü hem alt sınırları (Big-Omega) hem de üst sınırları (Big-Oh) belirtir. Ancak, genellikle en kötü durum senaryosunu belirten Big-Oh notasyonu, bir algoritmanın performansını analiz etmek için daha yaygın olarak kullanılır.

Big-Theta (Θ) notasyonu, bir algoritmanın karmaşıklığını en iyi ve en kötü durumların ortalaması olarak ifade eder. Θ notasyonunu bir Python kodu üzerinden örneklendirelim.

Bir algoritmanın karmaşıklığını belirtirken, genellikle işlem sayısı ve/veya hafıza kullanımı ile ilgilidir. Bu kod parçacığı, O(n) karmaşıklığa (lineer karmaşıklık) sahip bir işlemi temsil eder:

def lineer_karmaşıklıkta_örnek(liste):
    for eleman in liste:
        print(eleman)  # Bu işlemi her eleman için bir kez yapıyoruz.

Yukarıdaki kodda, eleman sayısı kadar işlem yapılıyor. Yani, listenin uzunluğu arttıkça, yapılacak işlem sayısı da doğru orantılı olarak artar. Bu durumda, bu fonksiyonun karmaşıklığı Θ(n)'dir.

Bir başka örnek olarak, O(1) karmaşıklığa (sabit karmaşıklık) sahip bir işlemi temsil eden kodu göz önünde bulundurabiliriz:

def sabit_karmaşıklıkta_örnek(liste):
    print(liste[0])  # Sadece ilk elemanı yazdırıyoruz. Eleman sayısı ne olursa olsun, bu işlemi sadece bir kez yapıyoruz.

Logaritmik karmaşıklığa sahip bir örnek aşağıdaki gibi bir ikili arama (binary search) algoritması olabilir:

def binary_search(arr, low, high, x): 
    if high >= low: 
        mid = (high + low) // 2
        if arr[mid] == x: 
            return mid 
        elif arr[mid] > x: 
            return binary_search(arr, low, mid - 1, x) 
        else: 
            return binary_search(arr, mid + 1, high, x) 
    else: 
        return -1

Bu örnekte, ikili arama her adımda problemi yarı yarıya böler ve bu da logaritmik zaman karmaşıklığına yol açar. Eğer listenin n elemanı varsa, ikili arama algoritması log2(n) adımda sonuç verir. Bu durumda, bu fonksiyonun karmaşıklığı Θ(log n)'dir.

Önemli olan şu ki, bu Θ(log n) karmaşıklığı, arama yapılacak listeye erişimin sürekli ve eşit zaman alması (yani, random-access model) ve listesinin sıralı olması durumlarında geçerlidir.