Toplamlar, recurrence ve Master teoremi

Özyinelemeli kodu analiz ederken çağrı sayısını, alt problem boyutunu ve çağrı dışındaki işi ayır. Merge sort için T(n)=2T(n/2)+Θ(n): iki yarı çözülür, birleştirme doğrusal iştir. Çağrı ağacının her seviyesinde toplam Θ(n), yaklaşık log₂n seviye vardır; sonuç Θ(n log n).

Master teoremi T(n)=aT(n/b)+f(n) biçimindeki dengeli bölmelere uygulanır. f(n)'yi n^(log_b a) ile karşılaştır; yalnız uygun koşullarda üç klasik durumu kullan. Eşitsiz alt problemler, n−1 küçülmesi veya salınımlı maliyetler için teoremi zorlamak yerine açılım, yerine koyma ve indüksiyon kullan.

T(n)=T(n−1)+n açıldığında n+(n−1)+…+1 olur. T(n)=T(n/2)+1 ise her seviyede sabit iş yapar. Recurrence'ın sınır koşulunu belirt: T(1)=Θ(1). Kesirli boyutlar floor/ceil ile ele alınır; çoğu büyüme sonucunda bunlar sabit fark oluşturur fakat doğruluk kodunda ihmal edilmez.

def halving_depth(n):
    if n < 1:
        raise ValueError("n must be positive")
    depth = 0
    while n > 1:
        n //= 2
        depth += 1
    return depth
assert halving_depth(8) == 3