Neden bir yöntem daha?
Master theorem bir kalıp makinesi: sadece $T(n) = a\,T(n/b) + O(n^d)$ biçimini yer. Recurrence bu kalıba uymuyorsa makine susar. Substitution method ise kalıp istemez. Cevabı bir yerden bulursun (unroll ederek, recursion tree çizerek, sayı deneyerek) ve doğru olduğunu ispatlarsın.
- $T(n) = T(n-1) + n$: problem bölünmüyor, size 1 azalıyor. $n/b$ biçimi yok, $b > 1$ bulamazsın.
- $T(n) = T(n/5) + T(7n/10) + cn$: iki subproblem'in size'ı farklı. Tek bir $a$ ve tek bir $b$ yok.
- $T(n) = 2T(n/2) + n\log n$: CS161'in master theorem'i $f(n) = n^d$ ister, $n\log n$ öyle değil. CLRS 3rd edition'daki sürümde de $n\log n$, $n^{\log_2 2} = n$'den büyük ama polynomially büyük değil; case 2 ile case 3 arasındaki boşluğa düşer.
- Guess: cevabın biçimini guess et, örneğin $T(n) \le c\, n\log n$.
- Prove: guess'i induction ile ispatla. Recurrence'ta $T$'nin küçük argümanlarının yerine guess'i koyarsın (substitute), yöntemin adı buradan gelir.
- Profit: ispat çalışınca bulduğun constant'larla temiz bir ispat yaz.
Hangisini master theorem doğrudan çözer?
Tarif: guess, induction, constant en son
Induction bir merdiven. Alt basamağı (base case) sağlam koyarsın. Sonra "altındaki bütün basamaklar sağlamsa bu basamak da sağlam" dersin. $T(n)$, $T(n/2)$'ye ya da $T(n/5)$ ile $T(7n/10)$'a dayandığı için hemen alttaki basamak yetmez; altındaki her basamağı varsayarız. Buna strong induction denir.
Oynat: $T(n) = 2T(n/2) + n$, $T(1) = 1$ ve guess $T(n) \le 2n\log n$. Her basamak bir alttaki basamağı kullanıyor; değerler JavaScript'te recurrence çalıştırılarak hesaplanıyor.
- Guess: $T(n) \le d\cdot g(n)$, $d$ henüz bilinmiyor.
- Inductive hypothesis (IH): $n_0 \le m < n$ olan her $m$ için $T(m) \le d\cdot g(m)$.
- Inductive step: recurrence'ı yaz, küçük $T$'lerin yerine IH'yi koy, sonucun $\le d\cdot g(n)$ olması için $d$'nin sağlaması gereken koşulu çıkar (örneğin $d \ge 10c$).
- Base case: $T(n_0) \le d\cdot g(n_0)$ için gereken koşulu çıkar (örneğin $d \ge 1$).
- İki koşulu birden sağlayan $d$'yi seç: $d = \max(1, 10c)$.
Hangi $d$'nin yeteceğini inductive step'i yapmadan bilemezsin. $d$'yi baştan "5" diye koyarsan ve inductive step $d \ge 10$ isterse ispat çöker. Guess yanlış değildir, sadece constant kötü seçilmiştir. Bu yüzden önce $d$'yi harf olarak taşırsın; inductive step ve base case sana koşulları verir, sonra sayıyı seçersin. Sınav kâğıdına ise constant'ı en baştan sayıyla yazarsın (Step 3: "pretend you knew it all along").
"Consider the recurrence $f(n) = f(n-1) * f(n-1)$, $f(1) = 2$. Show using induction that $f(n)$ is $\Omega(2^n)$."
Tarif aynı, iki farkla. Bound bu kez alttan: Ω, yani $f(n) \ge c\cdot 2^n$ ispatlanacak. $f(n)$ sadece $f(n-1)$'e baktığı için de bir alt basamak yeter, strong induction şart değil.
İpucu 1
Önce birkaç değer hesapla: $f(2) = 4$, $f(3) = 16$, $f(4) = 256$. Guess $f(n) \ge c\cdot 2^n$, $c$'yi harf olarak taşı. IH: $f(n-1) \ge c\cdot 2^{n-1}$.
İpucu 2
IH'yi iki çarpana da uygula (ikisi de pozitif, inequality bozulmaz): $f(n) \ge c^2\, 2^{2n-2}$. Bunun $\ge c\cdot 2^n$ olması için $c\cdot 2^{n-2} \ge 1$ gerekir; $n = 2$'de bu $c \ge 1$ demek. Base case $f(1) = 2 \ge 2c$ ise $c \le 1$ ister. Hangi $c$ kalıyor?
Çözümü göster
Claim. Her $n \ge 1$ için $f(n) \ge 2^n$. Dolayısıyla $f(n) = \Omega(2^n)$, $c = 1$, $n_0 = 1$.
Base case. $f(1) = 2 \ge 2^1$. ✓
IH. $n \ge 2$ için $f(n-1) \ge 2^{n-1}$.
Inductive step. $n \ge 2$ olsun. IH'ye göre $f(n-1) \ge 2^{n-1} > 0$, iki çarpanı da alttan sınırlayabiliriz: $f(n) = f(n-1)\cdot f(n-1) \ge 2^{n-1}\cdot 2^{n-1} = 2^{2n-2} = 2^n\cdot 2^{n-2} \ge 2^n$, çünkü $n \ge 2$ iken $2^{n-2} \ge 1$. ✓
Conclusion. Induction ile her $n \ge 1$ için $f(n) \ge 1\cdot 2^n$. Ω definition'ı $c = 1,\ n_0 = 1$ ile sağlanır. ∎
Constant neden 1? $c$'yi harf olarak taşırsan base case $c \le 1$, inductive step ($n = 2$'de) $c \ge 1$ verir; ikisini birden sağlayan tek değer $c = 1$. "Constant en son seçilir" kuralı burada tam iş başında. Not: gerçekte $f(n) = 2^{2^{n-1}}$, yani $2^n$'den çok daha hızlı büyür; soru sadece bu gevşek lower bound'u istiyor.
$T(n) = 2T(n/2) + n$ ispatında neden "sadece $n-1$ için doğru" varsayımı yetmez?
Sınav düzeni: 2T(n/2) + n ≤ 2n log n
$T(n) = 2T(n/2) + n$, $T(1) = 1$. Unroll et: $T(n) = 4T(n/4) + 2n = 8T(n/8) + 3n = \dots = 2^t T(n/2^t) + t\cdot n$. $t = \log n$ koyunca $T(n) = n + n\log n = n(\log n + 1)$. Guess: $T(n) \le C\, n\log n$.
Adım 2: C'yi harf olarak taşı
IH: $2 \le m < n$ için $T(m) \le C\,m\log m$. Recurrence'ta yerine koy ($n \ge 4$ ve ikinin kuvveti, $\log$'un base'i 2):
$$T(n) = 2T(n/2) + n \le 2C\tfrac n2 \log\tfrac n2 + n = Cn(\log n - 1) + n = Cn\log n - (C-1)n.$$Bu, $C \ge 1$ ise $\le Cn\log n$. Base case: $n = 1$'de $C\cdot 1 \cdot \log 1 = 0$ ve $T(1) = 1 \not\le 0$. O yüzden base'i $n_0 = 2$'de kurarız: $T(2) = 2\cdot 1 + 2 = 4 \le C\cdot 2\log 2 = 2C$ ⇒ $C \ge 2$. İkisini birden sağlayan: $C = 2$.
Claim. İkinin kuvveti olan her $n \ge 2$ için $T(n) \le 2n\log n$. Dolayısıyla $T(n) = O(n\log n)$, $c = 2$, $n_0 = 2$.
IH. $2 \le m < n$ olan her (ikinin kuvveti) $m$ için $T(m) \le 2m\log m$.
Base case. $T(2) = 4 = 2\cdot 2\cdot \log 2$. ✓
Inductive step. $n \ge 4$ olsun. $n/2 \ge 2$, IH $n/2$'ye uygulanır: $T(n) = 2T(n/2) + n \le 2\cdot 2\tfrac n2 \log\tfrac n2 + n = 2n\log n - 2n + n = 2n\log n - n \le 2n\log n.$ ✓
Conclusion. Induction ile her $n \ge 2$ için $T(n) \le 2n\log n$. Big-O definition'ı $c = 2,\ n_0 = 2$ ile sağlanır. ∎
- $n_0 = 1$ ile $\log$: $\log 1 = 0$, yani $n\log n$ guess'i $n = 1$'de hiçbir $c$ ile tutmaz. Base case'i $n = 2$'ye kaydır. Bunu yapabilirsin, çünkü Big-O zaten "$n \ge n_0$ için" der.
- IH'deki constant değişmez: IH'deki $C$ ile son satırdaki $C$ aynı sayı. Inductive step'in sonunda $C$ büyümüşse ispat yoktur (Bölüm 4).
- Floor/ceiling'i CS161 de atlar ("we're being sloppy"). Sınavda "$n$ ikinin kuvveti varsayalım" yazman yeterli.
$T(n) = 2T(n/2) + 32n$, $T(2) = 2$. $T(n) \le C\,n\log n$ olduğunu ispatla ve $C$'yi bul.
İpucu 1
Aynı hesap: $2C\tfrac n2\log\tfrac n2 + 32n = Cn\log n + (32 - C)n$.
İpucu 2
Inductive step $C \ge 32$ ister. Base case: $T(2) = 2 \le 2C$ ⇒ $C \ge 1$. Hangisi büyük?
Çözümü göster
$C = 32$. IH: $2 \le m < n$ için $T(m) \le 32m\log m$. Base case: $T(2) = 2 \le 64$. Inductive step: $T(n) \le 2\cdot 32\tfrac n2\log\tfrac n2 + 32n = 32n\log n - 32n + 32n = 32n\log n$. Conclusion: $T(n) = O(n\log n)$, $c = 32$, $n_0 = 2$.
Bir substitution ispatının "Conclusion" satırında ne olmalı?
Klasik hata: inductive step'in içinde "= O(n)"
"MergeSort $O(n)$'dir. Guess: $T(n) \le cn$. O zaman $T(n) = 2T(n/2) + n \le 2c\tfrac n2 + n = cn + n = O(n)$." Nerede hata var?
İpucu 1
IH ne söylüyordu? "$T(m) \le cm$", belirli bir $c$ ile. Inductive step'in sonunda ne elde etmen gerekiyordu?
İpucu 2
$cn + n \le cn$ hiç tutar mı? "$= O(n)$" yazınca constant'a ne oldu?
Çözümü göster
Inductive step'in son satırı tam olarak "$T(n) \le cn$" olmalı, aynı $c$ ile. Elde edilen $cn + n$ ise $cn$'den büyük: $cn + n \le cn \iff n \le 0$. İspat çöktü.
"$= O(n)$" yazmak constant'ı gizlice $c$'den $c + 1$'e çıkarır. Her level'de bir kez daha artar: $\log n$ level sonra constant $c + \log n$ olur, yani artık constant değildir. Gerçekten de $T(n) = n\log n + n$, yani $T(n)/n = \log n + 1$ sınırsız büyür. CS161 L4 notları §3.5 aynı hesabı yapar: $n + dn \le dn$ hiçbir $d$ ile tutmaz, guess yanlış.
- IH bir sayı ile yazılır: "$T(m) \le 10m$" ya da "$T(m) \le C m$, $C$ constant". "$T(m) = O(m)$" bir IH değildir.
- Inductive step'in son satırı IH ile aynı biçimde, aynı constant'la biter: $T(n) \le C\cdot g(n)$.
- Lower-order term'ler inductive step'te atılmaz. Bilkent slaydı: "MUST prove the EXACT inequality, CANNOT ignore lower order terms".
IH tek bir $n$ hakkında bir cümle olmalı. "$T(n) = O(n)$" ise "bir $C$ ve $n_0$ var ki her $n \ge n_0$ için…" der; tek bir $n$ hakkında hiçbir şey söylemez. Tek bir $n$ için her şey $O(1)$'dir. CS161'deki penguen örneğinde ($2T(n/2) + 32n$) aynı hata $O(n\log n)$ ile yapılır.
Hocanın listesinde açıkça var: "Find the flaw. What exactly must the last line of an inductive step say?" Sınavda bir "ispat" verilip hatayı bulman istenirse önce IH'deki constant'ı, sonra inductive step'in son satırını kontrol et.
Inductive step'in sonunda $T(n) \le Cn + 7$ çıktı, hedef $T(n) \le Cn$. Ne yaparsın?
Hypothesis'i güçlendir: 2T(n/2) + 1
$T(1) = 1$ ile: $T(2) = 3$, $T(4) = 7$, $T(8) = 15$, $T(16) = 31$. Desen: $T(n) = 2n - 1$. Yani $T(n) \le 2n$, claim $T(n) = O(n)$ doğru. Bakalım ispat ne diyor.
Deneme 1: IH $T(m) \le cm$
$T(n) = 2T(n/2) + 1 \le 2c\tfrac n2 + 1 = cn + 1$. Hedef $cn$. $cn + 1 \le cn$ hiçbir $c$ ile tutmaz. Takıldık.
Hayır. $T(n) = 2n - 1 \le 2n$, claim doğru. Çöken şey claim değil, ispat. IH çok zayıf: her recursive call'dan "en çok $c\cdot m$" bilgisi geliyor ve iki call'ın toplamı tam $cn$'e çıkıyor, $+1$'e yer kalmıyor.
Deneme 2: IH $T(m) \le cm - 1$
$T(n) \le 2\left(c\tfrac n2 - 1\right) + 1 = cn - 2 + 1 = cn - 1$. ✓ Her $c$ için tam olarak hedef. Base case: $T(1) = 1 \le c\cdot 1 - 1$ ⇒ $c \ge 2$. Seç $c = 2$: $T(n) \le 2n - 1 \le 2n$, yani $O(n)$, $c = 2$, $n_0 = 1$.
Induction'da IH hem ispatlaman gereken şey hem de kullandığın şey. Daha güçlü bir IH recursive call'lardan daha fazla bilgi getirir: her call "$-1$" kadar boşluk taşır, iki call'ın $-2$'si recurrence'ın $+1$'ini öder ve geriye hedefteki $-1$ kalır.
Oynat: her satırda gerçek $T(n)$ (recurrence'tan hesaplandı), zayıf IH'nin inductive step'te verdiği bound ve güçlü IH'nin verdiği bound, $c = 2$ ile.
Güçlü IH $T(m) \le cm - 1$ ile $T(1) = 1$ base case'i $c$'ye ne dayatır?
Lower-order term çıkar: 4T(n/2) + n, sonra Ω
2025-26'da derste kullanılan Bilkent slaytlarının ana örneği. $T(n) = 4T(n/2) + n$, $T(1) = \Theta(1)$.
IH $T(m) \le cm^3$. $T(n) \le 4c\left(\tfrac n2\right)^3 + n = \tfrac c2 n^3 + n = cn^3 - \left(\tfrac c2 n^3 - n\right)$. Parantez ("residual") $\ge 0$ ise bitti: $c \ge 2$, $n \ge 1$ yeter. Base case: $c$ yeterince büyük. Doğru ama tight değil.
IH $T(m) \le cm^2$. $T(n) \le 4c\tfrac{n^2}{4} + n = cn^2 + n$. Slayt burada "$= O(n^2)$" yazmanın yanlış olduğunu vurgular: $cn^2 + n \le cn^2$ tutmaz.
IH $T(m) \le c_1 m^2 - c_2 m$.
$$T(n) \le 4\left(c_1\tfrac{n^2}{4} - c_2\tfrac n2\right) + n = c_1n^2 - 2c_2 n + n = c_1n^2 - c_2n - (c_2 - 1)n \le c_1n^2 - c_2n \quad (c_2 \ge 1).$$Base case $T(1) = 1$ alırsak: $1 \le c_1 - c_2$ ⇒ $c_1 \ge c_2 + 1$. Seç $c_2 = 1,\ c_1 = 2$: $T(n) \le 2n^2 - n \le 2n^2$. (Kontrol: $T(1) = 1$ ile gerçek değer tam olarak $2n^2 - n$: 1, 6, 28, 120, …)
IH $T(m) \ge cm^2$. $T(n) = 4T(n/2) + n \ge 4c\tfrac{n^2}{4} + n = cn^2 + n \ge cn^2$. ✓ Güçlendirmeye gerek yok: fazladan $+n$ lower bound'da işimize yarar. Base case: $T(1) = 1 \ge c$ ⇒ $c = 1$. Sonuç: $n^2 \le T(n) \le 2n^2$, yani $T(n) = \Theta(n^2)$. Master theorem de aynısını der ($a = 4 > 2^1$).
- Θ için iki ayrı ispat gerekir: O ve Ω. Recurrence "$\le$" ile verilmişse sadece O ispatlanabilir.
- Fazlalık $+n$ ise çıkardığın term'in order'ı da $n$ olmalı ($-c_2n$). $-1$ çıkarmak $+n$'i ödemez.
- Ω ispatında base case $c$'yi küçük seçmeye zorlar, O ispatında büyük.
$T(n) = 4T(n/2) + n$ için IH $T(m) \le c_1m^2 - 5$ (constant çıkar) dersen ne olur?
Farklı size'lar: T(n/5) + T(7n/10) + cn
Root $cn$ iş yapar. Child'ların toplam size'ı $\tfrac n5 + \tfrac{7n}{10} = \tfrac{9}{10}n$, yani bir alttaki level'in işi en çok $\tfrac{9}{10}cn$. Level'lerin toplamı: $cn + 0.9cn + 0.81cn + \dots \le \dfrac{cn}{1 - 0.9} = 10cn$. Guess: $T(n) \le dn$ ve $d$ 10c civarında çıkmalı.
Önce tahmin et: $n = 1000$ ile $n/5 + 7n/10$ ağacında level 3'ün toplam size'ı kaç? $n/3 + 2n/3$ ağacında level toplamı kaçıncı level'de $n$'in altına düşer?
IH: $n_0 \le m < n$ için $T(m) \le dm$. Inductive step:
$$T(n) \le d\tfrac n5 + d\tfrac{7n}{10} + cn = \tfrac{9}{10}dn + cn \le dn \iff cn \le \tfrac{1}{10}dn \iff d \ge 10c.$$Base case: $T(1) = 1 \le d$. Seç $d = \max(1, 10c)$. Sonuç $T(n) = O(n)$.
10c nereden? Inductive step'te IH'den gelen kısım $\tfrac{9}{10}dn$; hedefe kadar kalan boşluk $\tfrac{1}{10}dn$. Bu boşluk root'un işi $cn$'i ödemeli: $\tfrac{1}{10}d \ge c$. Yani $10 = \dfrac{1}{1 - 9/10}$; kesirlerin toplamı 1'e ne kadar yakınsa $d$ o kadar büyür.
Önce tahmin et: $T(n/5) + T(7n/10) + n \le cn$ için inductive step'in geçtiği en küçük $c$ kaç? $c = 6$ ile grafikte kırmızı nokta görür müsün?
$T(n) \le n + T(n/5) + T(7n/10)$ ($n > 10$), $T(n) = 1$ ($1 \le n \le 10$). IH: $T(n) \le 10n$. Base case: $1 \le n \le 10$ için $1 = T(n) \le 10n$. Inductive step: $k > 10$, IH tüm $1 \le n < k$ için: $T(k) \le k + 10\tfrac k5 + 10\tfrac{7k}{10} = k + 2k + 7k = 10k$. Conclusion: $c = 10,\ n_0 = 1$ ile $T(n) = O(n)$.
"Her recurrence'a en uygun ifadeyi seç: (1) $\Theta(\log n)$ (2) $\Theta(n)$ (3) $\Theta(n\log n)$ (4) $\Theta(n^{\log_2 3})$ (5) $\Theta(n^3)$." Şıklardan biri: $T(n) = T(n/2) + T(n/10) + T(n/20) + n$.
İpucu 1
Master theorem kullanılamaz (üç farklı size). Kesirleri topla.
İpucu 2
$\tfrac12 + \tfrac1{10} + \tfrac1{20} = \tfrac{13}{20} < 1$. $T(n) \le dn$ için inductive step hangi $d$'yi ister? Lower bound için root'un işine bak.
Çözümü göster
Cevap (2) $\Theta(n)$.
O: IH $T(m) \le dm$. $T(n) \le \tfrac{13}{20}dn + n \le dn \iff \tfrac{7}{20}d \ge 1 \iff d \ge \tfrac{20}{7} \approx 2.86$. Base case: $T(1) = 1 \le d$. Seç $d = 3$: $T(n) \le 3n$.
Ω: root tek başına $n$ iş yapar, yani $T(n) \ge n$. İkisi birlikte $\Theta(n)$.
$T(n) = T(n/3) + T(n/2) + n$ için $T(n) \le dn$ ispatında inductive step hangi koşulu verir?
Kesirlerin toplamı 1 ya da daha fazlaysa
Class prep L3 S3'ün ikinci yarısı. Oynat: üç recurrence için $T(n)/n$, gerçekten çalıştırılarak hesaplanıyor (floor ile, $n \le 10$ iken $T(n) = 1$). $T(n) = O(n)$ ise bu oran bounded kalmalı.
Inductive step: $d\tfrac n5 + d\tfrac{4n}{5} + cn = dn + cn \le dn$? Hiçbir $d$ ile tutmaz: boşluk sıfır, root'un işini ödeyecek yer yok. Recursion tree'de her level tam $cn$ iş yapar ve yaklaşık $\log_{5/4} n$ level var ⇒ $\Theta(n\log n)$.
Doğru guess $T(n) \le dn\log n$ ile inductive step: $d\tfrac n5\log\tfrac n5 + d\tfrac{4n}5\log\tfrac{4n}5 + cn = dn\log n - dHn + cn$, burada $H = \tfrac15\log 5 + \tfrac45\log\tfrac54 \approx 0.72$. $d \ge c/H \approx 1.39c$ yeter.
Her level'in işi bir öncekinin $\tfrac54$ katı: iş aşağı doğru artar, çözüm $n$'den polynomially büyük. $\Theta(n^p)$, burada $p$, $(1/2)^p + (3/4)^p = 1$'in çözümü, $p \approx 1.51$. Bu exponent değerini bulmak vize kapsamı dışında; bilmen gereken: linear olamaz.
Median of medians'ta 5'li yerine 3'lü gruplar kullanırsan recurrence yaklaşık $T(n/3) + T(2n/3) + cn$ olur. Toplam tam 1: analiz sadece $O(n\log n)$ verir, $O(n)$ değil. 5'li gruplarla $\tfrac15 + \tfrac7{10} = \tfrac9{10} < 1$, bu yüzden linear. Ayrıntısı Select dersinde.
- Toplam $< 1$ ⇒ $\Theta(n)$, root'un işi baskın.
- Toplam $= 1$ ⇒ $\Theta(n\log n)$, her level eşit.
- Toplam $> 1$ ⇒ $n^{p}$, $p > 1$; leaf'ler baskın.
Master theorem'deki üç case'e benziyor: root, denge, leaf'ler.
$T(n) = T(n/4) + T(3n/4) + n$ için $T(n) \le dn$ adımında ne olur?
Azalan recurrence: T(n−1) + n²
$T(1) = 1$ ile: $T(n) = n^2 + (n-1)^2 + \dots + 1^2 = \dfrac{n(n+1)(2n+1)}{6} \approx \dfrac{n^3}{3}$. Değerler: 1, 5, 14, 30, 55, 91. Guess: $\Theta(n^3)$.
Burada $T(n)$ sadece $T(n-1)$'e bakar, ordinary induction yeter. IH $T(n-1) \le c(n-1)^3$:
$$T(n) \le c(n-1)^3 + n^2 = cn^3 - 3cn^2 + 3cn - c + n^2.$$$\le cn^3$ olması için $(1 - 3c)n^2 + 3cn - c \le 0$ gerekir. $c = 1$: $-2n^2 + 3n - 1 = -(2n-1)(n-1) \le 0$, her $n \ge 1$ için. ✓ Base case: $T(1) = 1 \le 1\cdot 1^3$. ✓ Conclusion: $T(n) \le n^3$, $c = 1,\ n_0 = 1$.
Aynı expansion, ters yön: $(1-3c)n^2 + 3cn - c \ge 0$ gerekir. $c = \tfrac13$: $0\cdot n^2 + n - \tfrac13 \ge 0$, her $n \ge 1$ için. ✓ Base case: $T(1) = 1 \ge \tfrac13$. ✓ Conclusion: $\tfrac13 n^3 \le T(n) \le n^3$, yani $\Theta(n^3)$.
- Guess $cn^2$ çöker: $c(n-1)^2 + n^2 = cn^2 - 2cn + c + n^2 \le cn^2$ için $n^2 - 2cn + c \le 0$ gerekir, büyük $n$'de tutmaz. Burada güçlendirme kurtarmaz, guess gerçekten küçük.
- Upper bound'da $c = \tfrac13$ olmaz: $(1-1)n^2 + n - \tfrac13 \le 0$ yanlış. Tight constant lower bound'un constant'ı; upper bound biraz pay ister.
- "$n - 1$" master theorem'e girmez (Bölüm 1).
Aynı soru, aynı beş şık: "$T(n) = T(n-1) + n^2$". İpucu olarak kâğıtta $\sum_{i=0}^{t} i^2 = \Theta(t^3)$ verilmişti.
İpucu 1
$T(n)$'yi unroll edip bir toplam olarak yaz. Kâğıttaki ipucu tam olarak bu toplamı veriyor.
İpucu 2
Gerekçeyi istersen substitution ile sağlamlaştır: $c = 1$ upper bound, $c = \tfrac13$ lower bound.
Çözümü göster
Cevap (5) $\Theta(n^3)$. $T(n) = T(1) + \sum_{i=2}^{n} i^2 = \sum_{i=1}^{n} i^2 = \tfrac{n(n+1)(2n+1)}{6} = \Theta(n^3)$ ($T(1) = 1$ alınırsa; $T(1) = O(1)$ başka bir constant ise fark da constant kadardır).
Induction ile: yukarıdaki iki kutu, $\tfrac13 n^3 \le T(n) \le n^3$, her $n \ge 1$ için.
$T(n) = T(n-1) + n^2$ ispatında neden strong induction şart değil?
Alıştırma: Fibonacci ve çıkmış soru
$F(0) = 0,\ F(1) = 1,\ F(n+2) = F(n) + F(n+1)$. (a) $F(n) = O(2^n)$ olduğunu, (b) $F(n) = \Omega(1.5^n)$ olduğunu induction ile göster. Base case, inductive step ve conclusion ayrı ayrı görünsün.
İpucu 1
$F(n)$ iki önceki değere bakar, bu yüzden iki base case gerekir ve IH "$m < n$ olan her $m$ için" kurulur.
İpucu 2
(a) için $c = 1$ dene: $2^{n-1} + 2^{n-2} = 3\cdot 2^{n-2}$ ile $2^n = 4\cdot 2^{n-2}$'yi karşılaştır.
İpucu 3
(b) için $1.5^{n-1} + 1.5^{n-2} = 1.5^{n-2}(1.5 + 1) = 2.5\cdot 1.5^{n-2}$ ve $1.5^n = 2.25\cdot 1.5^{n-2}$. $F(0) = 0$ hiçbir pozitif $c\cdot 1.5^0$'dan büyük olamaz: base case'leri $n = 1, 2$'de kur.
Çözümü göster
(a) Claim: her $n \ge 0$ için $F(n) \le 2^n$. Base case: $F(0) = 0 \le 1$, $F(1) = 1 \le 2$. IH: $0 \le m < n$ için $F(m) \le 2^m$. Inductive step ($n \ge 2$): $F(n) = F(n-1) + F(n-2) \le 2^{n-1} + 2^{n-2} = 3\cdot 2^{n-2} \le 4\cdot 2^{n-2} = 2^n$. Conclusion: $F(n) = O(2^n)$, $c = 1,\ n_0 = 0$.
(b) Claim: her $n \ge 1$ için $F(n) \ge \tfrac13\, 1.5^n$. Base case: $F(1) = 1 \ge 0.5$, $F(2) = 1 \ge 0.75$. IH: $1 \le m < n$ için $F(m) \ge \tfrac13 1.5^m$. Inductive step ($n \ge 3$): $F(n) = F(n-1) + F(n-2) \ge \tfrac13 1.5^{n-2}(1.5 + 1) = \tfrac13\cdot 2.5\cdot 1.5^{n-2} \ge \tfrac13\cdot 2.25\cdot 1.5^{n-2} = \tfrac13 1.5^n$. Conclusion: $F(n) = \Omega(1.5^n)$, $c = \tfrac13,\ n_0 = 1$.
"$T(2) = 1$, $T(n) = T(n^{1/4}) + 1$ ($n > 1$). Solve this recurrence asymptotically. Show your work." (2019-20 vizesinde aynısı $T(n^{1/2})$ ile.) Önce unroll ederek çöz, sonra cevabı substitution ile doğrula.
İpucu 1
$n = 2^{4^k}$ al. $n^{1/4} = 2^{4^{k-1}}$. Kaç adımda 2'ye inersin?
İpucu 2
$k$ adım: $T(n) = k + 1$ ve $\log_2 n = 4^k$ ⇒ $k = \log_4\log_2 n$. Şimdi IH $T(m) = \log_4\log m + 1$ ile inductive step'i yap: $\log(n^{1/4}) = \tfrac14\log n$.
Çözümü göster
Unrolling: $T(n) = T(n^{1/4}) + 1 = T(n^{1/16}) + 2 = \dots = T(n^{1/4^k}) + k$. $n^{1/4^k} = 2$ olduğunda $\log n = 4^k$, $k = \log_4\log n$. $T(n) = 1 + \log_4\log n = \Theta(\log\log n)$.
Substitution ile doğrulama ($n = 2^{4^k}$ biçimindeki $n$'ler için). Claim: $T(n) = \log_4\log n + 1$. Base case: $n = 2$: $\log_4 1 + 1 = 1 = T(2)$. ✓ Inductive step: $T(n) = T(n^{1/4}) + 1 = \log_4\!\left(\tfrac14\log n\right) + 1 + 1 = \log_4\log n - 1 + 2 = \log_4\log n + 1$. ✓ Conclusion: $T(n) = \Theta(\log\log n)$.
Altungöz'ün cevaplı kâğıdında aynı unrolling ile $O(\log\log n)$ bulunmuş.
CS161 L3 concept check: $T(n) = 2T(n/2) + 3T(n/3) + n^2$. Substitution ile ispatlanabilen en tight guess hangisi?
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
Hangisi geçerli bir inductive hypothesis?
$T(n) = 2T(n/2) + 1$ için $T(m) \le cm$ ile inductive step $cn + 1$ verdi. Doğru yorum?
$T(n) = T(n/5) + T(7n/10) + cn$ ispatında $d \ge 10c$ koşulu nereden çıkar?
$T(n) = T(n-1) + n^2$, $T(1) = 1$. Hangi ifade doğru?