Recurrence kurmak
MergeSort array'i ikiye böler, iki yarıyı kendini çağırarak sort eder, sonra $n$ adımda merge eder. "Size $n$ için running time" = "size $n/2$ için iki running time" + "merge":
$$T(n) = 2\,T(n/2) + n, \qquad T(1) = 1$$Buna recurrence denir: fonksiyon kendi küçük değerleri cinsinden tanımlanır.
- Kaç recursive call var? → $a$
- Her call hangi size'da? → $n/b$ (ya da $n-1$, $\sqrt n$…)
- Call'ların dışında ne kadar iş var (divide + combine)? → $f(n)$
Foo(n):
if n <= 1: return 1
s = 0
for i = 1..n: s = s + 1 // n iş
return Foo(n/3) + Foo(n/3) + Foo(n/3) + Foo(n/3)Dört recursive call var, her biri $n/3$ size'ında, dışarıda $n$ iş: $T(n) = 4T(n/3) + n$. Aynı kodda x = Foo(n/3) yazıp 4*x döndürseydin tek call olurdu: $T(n) = T(n/3) + n$. Sonucun kaç kez kullanıldığını değil, call sayısını say.
| Algoritma | Recurrence | Neden |
|---|---|---|
| Mult1 (4 multiplication) | $4T(n/2) + O(n)$ | $ac, ad, bc, bd$ + addition'lar |
| Karatsuba | $3T(n/2) + O(n)$ | $ad+bc = (a+b)(c+d) - ac - bd$ |
| Binary search | $T(n/2) + O(1)$ | middle element'e bak, tek yarıda devam et |
| Powering $a^n$ | $T(n/2) + O(1)$ | val = POWER(a, n/2), sonra val*val |
| Matrix multiplication (block) | $8T(n/2) + \Theta(n^2)$ | 8 recursive multiplication, matrix addition'lar |
| Strassen | $7T(n/2) + \Theta(n^2)$ | 7 recursive multiplication yetiyor |
return POWER(a, n/2) * POWER(a, n/2)yazarsan iki recursive call olur: $T(n) = 2T(n/2) + 1 = \Theta(n)$. Bütün kazanç gider.- Recurrence "$\le$" ile verilmişse (örneğin $T(n) \le 2T(n/2) + n$) sadece upper bound, yani $O$ çıkar. Θ diyebilmek için lower bound'u da göstermelisin.
- Base case'i unutma: "$T(1) = O(1)$" ya da soruda verilen değer ($T(2) = 1$ gibi).
countOperations(n): $n \times n$ nested loop ile bir counter'ı artırıyor, sonra countOperations(n / 2) sonucunu ekleyip döndürüyor. Big-Oh complexity'si nedir?
İpucu 1
Önce recurrence'ı kur: fonksiyon kendini kaç kez ve hangi size ile çağırıyor? Recursive call'un dışındaki iki loop toplam kaç iteration yapıyor?
İpucu 2
$a$, $b$, $d$'yi oku ve $a$ ile $b^d$'yi karşılaştır: tree'nin hangi kısmı baskın?
Powering: val = POWER(a, n/2); return val * val (n çift). Recurrence hangisi?
Recursion tree: level tablosu
Her node bir subproblem'dir. Node'un içine o call'un kendi işini yaz (child'ların işi hariç). $T(n)$, bütün node'ların toplamıdır. En kolayı bunu level level toplamak, çünkü bir level'deki bütün node'lar aynı size'dadır.
Bir recurrence seç ve oynat. Tree gerçekten açılıyor (her node $a$ child'a ayrılıyor) ve her satırdaki sayılar bu açılımdan sayılarak bulunuyor. Kolaylık olsun diye $n = b^4$ ve $T(1) = c$.
| Level | Problem sayısı | Her birinin size'ı | Level'deki iş |
|---|---|---|---|
| 0 | 1 | $n$ | $c\,n^d$ |
| 1 | $a$ | $n/b$ | $a\,c\,(n/b)^d$ |
| $t$ | $a^t$ | $n/b^t$ | $a^t c\,(n/b^t)^d = c\,n^d \left(\dfrac{a}{b^d}\right)^t$ |
| $\log_b n$ | $a^{\log_b n} = n^{\log_b a}$ | 1 | $c\, n^{\log_b a}$ |
Yani her level bir öncekinin $a/b^d$ katıdır. Sonucu bu oran belirler.
- Depth $\log_b n$'dir, her zaman $\log_2 n$ değil: $T(n/4)$ ise $\log_4 n$ level vardır.
- Leaf sayısı $n$ değil, $a^{\log_b n} = n^{\log_b a}$. MergeSort'ta ($a = b = 2$) bu sayı tesadüfen $n$'ye eşit.
- "Bir node'un işi" ile "level'in işi"ni karıştırma: level işi = node sayısı × node başına iş.
CS161 concept check · $T(n) = 5T(n/4) + 2n$
Yukarıdaki menüde bu recurrence var. Önce tabloyu kendin doldur, sonra oynatıp kontrol et.
Level 4'te (root level 0) kaç problem var?
Level $i$'nin toplam katkısı nedir?
$T(n)$ için hangisi doğru? ($\log_4 5 \approx 1.16$)
n=64 için (problem sayısı, boyut, toplam iş) seviyeleri (1,64,64), (3,16,48), (9,4,36). a,b,d ve kapalı toplamı bul; Master theorem kullanma.
İpucu
Çözümü göster
a=3,b=4,d=1. t. seviyede 3^t problem, boyut n/4^t, iş n(3/4)^t. h=log₄n; h+1 seviye. Yapraklar 3^h. Geometric sum: T(n)=4n−3n^(log₄3)=Θ(n). n=64 için 64+48+36+27=175.
Geometric series: root mu, leaf'ler mi?
İki etki birbirine karşı çalışıyor. Branching ($a$) subproblem sayısını hızla artırır ve işi aşağı iter. Size'ın küçülmesi ($b^d$) alttaki subproblem'leri ucuzlatır ve işi yukarıda tutar. Hangisinin kazandığını $r = a/b^d$ söyler.
- $r < 1$: ilk term baskın. Toplam $1$ ile $\frac{1}{1-r}$ arasında, yani $\Theta(1)$.
- $r = 1$: bütün term'ler 1'dir. Toplam $N + 1$.
- $r > 1$: son term baskın. Toplam $r^N$ ile $r^N \cdot \frac{r}{r-1}$ arasında, yani $\Theta(r^N)$.
$N = \log_b n$ alıp önüne $c\,n^d$ çarpanını koyunca:
| Case | Resim | Sonuç | Slayt örneği |
|---|---|---|---|
| $a < b^d$ | Root-heavy: tall and skinny, iş tepede | $\Theta(n^d)$ | $T(n/2) + n = \Theta(n)$ |
| $a = b^d$ | Balanced: her level aynı | $\Theta(n^d \log n)$ | $2T(n/2) + n = \Theta(n\log n)$ |
| $a > b^d$ | Leaf-heavy: bushy, iş en altta | $\Theta(n^{\log_b a})$ | $4T(n/2) + n = \Theta(n^2)$ |
Üçüncü satırda: $n^d \cdot (a/b^d)^{\log_b n} = n^d \cdot \dfrac{a^{\log_b n}}{n^d} = n^{\log_b a}$, yani leaf sayısı.
Üç tree yan yana
Tablodaki üç örnek aynı $b = 2$ ve aynı $f(n) = n$'yi kullanıyor, sadece $a$ farklı. Üçünü aynı anda level level aç: her node'un içinde kendi size'ı yazıyor, her level'in altında o level'deki toplam iş var.
Önce tahmin et: $n = 16$ için her tree'nin leaf level'inde (size 1) toplam kaç birim iş olur?
- $n + n + n + \dots$ ($\log n$ term)
- $n + n/2 + n/4 + n/8 + \dots$ ($\log n$ term)
- $n + n + n + \dots$ ($n$ term)
- $n + n/2 + n/3 + n/4 + \dots + n/n$
Cevapları göster
- $n\log n$: balanced tree (MergeSort).
- $\le 2n$, yani $\Theta(n)$: oran $\tfrac12$, ilk term baskın.
- $n^2$.
- $n\,(1 + \tfrac12 + \dots + \tfrac1n) = n H_n = \Theta(n\log n)$: harmonic series, $H_n \approx \ln n$. Geometric değil, term'ler çok yavaş küçülüyor.
S18: Master theorem'in üç case'ini ezberden yaz. Her case'te işin root'ta mı, leaf'lerde mi toplandığını, yoksa level'lere eşit mi dağıldığını açıkla.
S22: $b$ ve $f(n)$ aynı kalırken $a$'yı iki katına çıkarırsan sonuç nasıl değişir? Bu sezgisel olarak neden mantıklı?
İpucu 1
Her şeyi $r = a/b^d$ ile düşün. $a$ iki katına çıkınca $r$ ne olur?
İpucu 2
Başlangıçtaki üç case'i ayrı ayrı dene: $r < 1$, $r = 1$, $r > 1$. Örnek: $2T(n/2) + n$'den $4T(n/2) + n$'ye geç.
Çözümü göster
S18: Level $t$'deki iş $c\,n^d r^t$, burada $r = a/b^d$. $r < 1$ ise level'ler geometric olarak küçülür ve root'un işi ($c\,n^d$) toplamın constant bir kesridir ⇒ $\Theta(n^d)$. $r = 1$ ise $\log_b n + 1$ level'in her biri $c\,n^d$ iş yapar ⇒ $\Theta(n^d\log n)$. $r > 1$ ise level'ler büyür ve son level (leaf'ler, $n^{\log_b a}$ tane) toplamın constant bir kesrini taşır ⇒ $\Theta(n^{\log_b a})$.
S22: $a \to 2a$ ise $r \to 2r$: branching artar, iş aşağı kayar. Balanced case leaf-heavy olur: $2T(n/2) + n = \Theta(n\log n)$ iken $4T(n/2) + n = \Theta(n^2)$. Leaf-heavy case'te exponent $\log_b 2$ kadar artar ($\log_b 2a = \log_b a + \log_b 2$). Root-heavy case'te $2a$ hâlâ $b^d$'den küçükse sonuç değişmez: $T(n/2) + n^2$ ve $2T(n/2) + n^2$ ikisi de $\Theta(n^2)$. $2a = b^d$ olursa bir $\log n$ çarpanı eklenir.
$n + \tfrac n2 + \tfrac n3 + \dots + \tfrac nn$ toplamı nedir?
Master theorem
$a \ge 1$, $b > 1$ ve $d$, $n$'den bağımsız constant'lar olsun. $T(n) = a\,T(n/b) + O(n^d)$ ise
$$T(n) = \begin{cases} O(n^d \log n) & a = b^d \\ O(n^d) & a < b^d \\ O(n^{\log_b a}) & a > b^d \end{cases}$$$a$: subproblem sayısı · $b$: size'ın küçülme çarpanı · $d$: divide + combine işinin exponent'i. İş term'i $\Theta(n^d)$ ise ve recurrence bir eşitlikse sonuçlar da Θ olur. $n/b$ yerine $\lfloor n/b \rfloor$ ya da $\lceil n/b \rceil$ olması sonucu değiştirmez.
- $a$, $b$, $d$'yi oku (constant çarpanları at: $10\sqrt n$ ⇒ $d = \tfrac12$; constant iş ⇒ $d = 0$).
- $b^d$'yi hesapla, $a$ ile karşılaştır.
- Case'i yaz ve sonucu ver. Sınavda "$a = 4,\ b = 2,\ d = 1,\ a > b^d$" satırını mutlaka yaz.
Kendin dene: a, b, d explorer
Slider'ları oynat ya da kutulara kendi değerini yaz. Bar'lar ilk yedi level'in işini root'un işine göre gösteriyor ($n = b^6$ ile level tablosundan hesaplanıyor). Altta recurrence gerçekten çalıştırılıyor ve $T(n)$ bulunan Θ'ya bölünüyor: oran bir constant'a yaklaşıyorsa sonuç doğru.
Önce tahmin et: Karatsuba'da ($a = 3$, $b = 2$, $d = 1$) level 6'nın işi root'un kaç katı olur, 1'den büyük mü küçük mü?
| Recurrence | $a, b, d$ | Comparison | Sonuç | Nereden |
|---|---|---|---|---|
| $4T(n/2) + n$ | 4, 2, 1 | $4 > 2$ | $\Theta(n^2)$ | Mult1 · 2025-26 s.41 |
| $3T(n/2) + n$ | 3, 2, 1 | $3 > 2$ | $\Theta(n^{\log_2 3}) \approx n^{1.585}$ | Karatsuba · CS161 s.21 |
| $2T(n/2) + n$ | 2, 2, 1 | $2 = 2$ | $\Theta(n\log n)$ | MergeSort · class prep S19 |
| $T(n/2) + n$ | 1, 2, 1 | $1 < 2$ | $\Theta(n)$ | CS161 s.21 · tam median pivot ile Select |
| $T(n/2) + 1$ | 1, 2, 0 | $1 = 2^0$ | $\Theta(\log n)$ | binary search, powering |
| $8T(n/2) + n^2$ | 8, 2, 2 | $8 > 4$ | $\Theta(n^3)$ | block matrix multiplication |
| $7T(n/2) + n^2$ | 7, 2, 2 | $7 > 4$ | $\Theta(n^{\log_2 7}) \approx n^{2.81}$ | Strassen |
| $4T(n/2) + n^2$ | 4, 2, 2 | $4 = 4$ | $\Theta(n^2\log n)$ | 2025-26 s.42 |
| $4T(n/2) + n^3$ | 4, 2, 3 | $4 < 8$ | $\Theta(n^3)$ | 2025-26 s.43 |
| $3T(n/2) + n^2$ | 3, 2, 2 | $3 < 4$ | $\Theta(n^2)$ | S2 §3 |
| $3T(n/81) + 10\sqrt{\sqrt n}$ | 3, 81, ¼ | $81^{1/4} = 3$ | $\Theta(n^{1/4}\log n)$ | CS161 concept check S2 |
- $\log_b a$, $\log_a b$ değil: $3T(n/2)$ için $\log_2 3 \approx 1.585$.
- $d$ bir exponent: $\sqrt{\sqrt n} = n^{1/4}$, $n\sqrt n = n^{3/2}$. Constant iş için $d = 0$, $n^0 = 1$.
- $d$ kesirliyse comparison'ı dikkatli yap: $3T(n/2) + n^{3/2}$ için $2^{1.5} \approx 2.83 < 3$ ⇒ leaf-heavy.
- Öndeki constant ($30n$, $10\sqrt{\sqrt n}$) ne case'i ne de sonucu değiştirir.
1.1 $T(n) = 6T(n/3) + n^3$ için tight bound'u söyle ve kanıtla. 1.2 $T(n) = 4T(n/5) + n$ için recursion tree ile bir upper bound ver.
İpucu 1
1.1: $3^3 = 27$ ile 6'yı karşılaştır. "Tight" için Θ gerekir; lower bound root'un işinden gelir.
İpucu 2
1.2: Tabloyu doldur: level $t$'de $4^t$ problem var, size $n/5^t$. Level işi $n(4/5)^t$. Oranı 1'den küçük bir geometric sum çıkıyor.
Çözümü göster
1.1: $a = 6$, $b = 3$, $d = 3$, $b^d = 27 > 6$ ⇒ Master theorem ile $T(n) = O(n^3)$. Root'ta zaten $n^3$ iş var, yani $T(n) \ge n^3$ ⇒ $\Omega(n^3)$. Birlikte $T(n) = \Theta(n^3)$.
1.2: Level $t$: $4^t$ problem, her biri $n/5^t$, toplam $4^t \cdot n/5^t = n(4/5)^t$. $\log_5 n + 1$ level. $T(n) \le n\sum_{t\ge0}(4/5)^t = n \cdot \frac{1}{1 - 4/5} = 5n$ ⇒ $T(n) = O(n)$. (Kontrol: $n = 5^{10}$'da $T(n)/n \approx 4.57 \le 5$.)
"For each of the questions below, please give the answer in terms of theta notation. (d) Solution to the recurrence $T(n) = 8T(n/2) + \sqrt n$" (sorunun bu bölümle ilgili kısmı)
İpucu 1
$\sqrt n$'yi $n^d$ biçiminde yaz. $d$ kaç?
İpucu 2
$b^d = 2^{1/2} \approx 1.41$. Bunu $a = 8$ ile karşılaştır: tree'nin hangi ucu baskın?
Çözümü göster
$a = 8$, $b = 2$, $d = \tfrac12$. $b^d = \sqrt 2 \approx 1.41 < 8 = a$ ⇒ leaf-heavy ⇒ $T(n) = \Theta(n^{\log_2 8}) = \boxed{\Theta(n^3)}$.
Neden: leaf sayısı $8^{\log_2 n} = n^3$. Her level bir öncekinin $8/\sqrt2 \approx 5.66$ katı iş yapıyor, root'taki $\sqrt n$ bu büyümenin yanında önemsiz kalıyor.
Kontrol: $T(1) = 1$ ve $n = 2^k$ için açık form $T(n) = n^3 + \dfrac{n^3 - \sqrt n}{4\sqrt2 - 1}$. Yani $T(n)/n^3 \to 1 + \frac{1}{4\sqrt2 - 1} \approx 1.21$, sabit bir sayı.
"(b) (15 points) For each recurrence, choose the expression (1)-(5) below which most accurately describes it. Note that not all options need to be used, and some options may be used more than once. If it helps, $\log_2(3) \approx 1.6$, and $\sum_{i=0}^{t} i^2 = \theta(t^3)$. Assume that $T(1) = O(1)$ and don't worry about floors and ceilings.
(1) $\theta(\log n)$ (2) $\theta(n)$ (3) $\theta(n\log n)$ (4) $\theta(n^{\log_2 3})$ (5) $\theta(n^3)$
- $T(n) = 3T(n/2) + n^{3/2}$
- $T(n) = 3T(n/2) + n$"
(sorunun bu bölümle ilgili kısmı; diğer üç recurrence Bölüm 6, 7 ve 8'de)
İpucu 1
İkisinde de $a = 3$, $b = 2$. Sadece $d$ değişiyor: $\tfrac32$ ve $1$. Her biri için $b^d$'yi hesapla.
İpucu 2
$2^{3/2} = 2\sqrt2 \approx 2.83$. Bu 3'ten büyük mü, küçük mü? Soruda verilen $\log_2 3 \approx 1.6$ da $\tfrac32$ ile karşılaştırmaya yarar.
Çözümü göster
1. recurrence: $a = 3$, $b = 2$, $d = \tfrac32$, $b^d = 2\sqrt2 \approx 2.83 < 3$ ⇒ leaf-heavy ⇒ $\Theta(n^{\log_2 3})$ ⇒ (4). Aynı şeyi exponent'lerle de görebilirsin: $\log_2 3 \approx 1.585 > 1.5$, yani leaf'lerin toplamı $n^{1.585}$, root'taki $n^{1.5}$ işten büyük.
2. recurrence: $a = 3$, $b = 2$, $d = 1$, $b^d = 2 < 3$ ⇒ $\Theta(n^{\log_2 3})$ ⇒ (4). Bu Karatsuba'nın recurrence'ı.
İkisi de aynı seçeneğe gidiyor. Soru "some options may be used more than once" diyerek buna izin veriyor.
Kontrol: $T(1) = 1$ ile ikincisinin açık formu $T(n) = 3n^{\log_2 3} - 2n$. Birincisinde oran $3/2^{1.5} \approx 1.06$, 1'e çok yakın; bu yüzden $T(n)/n^{\log_2 3}$ yavaş yavaş $\approx 17.5$'e yaklaşıyor ama sonuç yine $\Theta(n^{\log_2 3})$.
"(d) (10 points) Allie and Brandon each have come up with a divide-and-conquer algorithm to solve a problem.
- Allie's algorithm splits a problem of size $n$ into four pieces, each of size $n/2$, solves the pieces recursively, and takes time $30n$ to combine the results.
- Brandon's algorithm takes time $n^3$ to turn a problem of size $n$ into a smaller problem of size $n/2$, which it then solves recursively.
Write recurrences for the runtime of Allie's algorithm, $T_A(n)$, and the runtime of Brandon's algorithm, $T_B(n)$. Find which algorithm has an asymptotically better runtime by solving each recurrence."
İpucu 1
Her cümleyi Bölüm 1'deki üç soruya çevir: kaç call, hangi size, dışarıda ne kadar iş? "$30n$" ve "$n^3$" dışarıdaki iş.
İpucu 2
$T_A(n) = 4T_A(n/2) + 30n$, $T_B(n) = T_B(n/2) + n^3$. Şimdi her birinde $a$ ile $b^d$'yi karşılaştır.
Çözümü göster
Allie: $T_A(n) = 4T_A(n/2) + 30n$. $a = 4$, $b = 2$, $d = 1$, $b^d = 2 < 4$ ⇒ leaf'ler baskın ⇒ $T_A(n) = \Theta(n^{\log_2 4}) = \Theta(n^2)$. 30 constant'ı sonucu değiştirmez.
Brandon: $T_B(n) = T_B(n/2) + n^3$. $a = 1$, $b = 2$, $d = 3$, $b^d = 8 > 1$ ⇒ root baskın ⇒ $T_B(n) = \Theta(n^3)$. (Tree'de level'ler $n^3, n^3/8, n^3/64, \dots$, toplam $\le \tfrac87 n^3$.)
Sonuç: $n^2 = o(n^3)$, yani dört subproblem çözmesine rağmen Allie'nin algoritması asymptotically daha iyi.
Kontrol: $T(1) = 1$ ve $n = 2^k$ için $T_A(n) = 31n^2 - 30n$, $T_B(n) = \tfrac87(n^3 - 1) + 1$.
$T(n) = 9T(n/3) + n^2$ nedir?
Master theorem ne zaman uygulanmaz?
- Subproblem'ler aynı size'da değil: $T(n/5) + T(7n/10) + n$, $T(n/3) + T(2n/3) + n$.
- Size bölünmüyor, azalıyor: $T(n-1) + n$. $n/b$ formunda değil.
- İş $n^d$ formunda değil: $n\log n$, $n^2/\log n$, $2^n$.
- $a$ ya da $b$ constant değil ($\sqrt n\,T(\sqrt n) + n$), ya da $a < 1$.
"Uygulanmaz", "çözülmez" anlamına gelmez. Recursion tree ile topla, unrolling yap, change of variables uygula ya da substitution ile ispatla.
Akla ilk gelen ama yanlış cevap: "$a = b^d$ gibi, $\Theta(n\log n)$". $n\log n$, $n^1$ değil; $n^{1+\epsilon}$ de değil. Tree ile topla ($n = 2^k$):
$$\text{seviye } t:\ 2^t \cdot \frac{n}{2^t}\log\frac{n}{2^t} = n(k - t) \quad\Rightarrow\quad \sum_{t=0}^{k-1} n(k-t) = n\,\frac{k(k+1)}{2} = \Theta(n\log^2 n)$$2025-26 slaytlarındaki genel Case 2 ($f(n) = \Theta(n^{\log_b a}\log^k n)$ ⇒ $\Theta(n^{\log_b a}\log^{k+1} n)$, burada $k = 1$) aynı sonucu verir.
$n^{\log_2 4} = n^2$. $f(n) = n^2/\log n$ ondan küçük ama polynomially küçük değil: aradaki oran $\log n$ ve bu hiçbir $n^\epsilon$'a yetişmez. Slayt: "Master method does not apply". Tree yine çözer: level $t$'nin işi $4^t \cdot \frac{(n/2^t)^2}{\log(n/2^t)} = \frac{n^2}{k - t}$, toplam $n^2\left(\frac1k + \frac1{k-1} + \dots + 1\right) = n^2 H_k = \Theta(n^2\log\log n)$.
$f(n)$'yi $n^{\log_b a}$ ile karşılaştırır: (1) polynomially küçükse $\Theta(n^{\log_b a})$; (2) aynıysa $\Theta(n^{\log_b a}\log n)$; (3) polynomially büyükse ve regularity condition $a f(n/b) \le c f(n)$, $c < 1$ sağlanıyorsa $\Theta(f(n))$. $f = n^d$ iken CS161 versiyonuyla aynı sonucu verir; $4T(n/2) + n^3$'te regularity $4(n/2)^3 = \tfrac12 n^3$ ile sağlanır.
Master theorem şunları neden çözemez: $T(n) = T(n-1) + n$, $T(n) = T(n/5) + T(7n/10) + cn$, $T(n) = 2T(n/2) + n\log n$? Teoremin şartlarının bozulduğu bir $aT(n/b) + f(n)$ örneği ver.
İpucu 1
Her biri için sor: $n/b$ formunda tek bir subproblem size'ı var mı? İş term'i $n^d$ formunda mı?
İpucu 2
Üçünü de çözebilirsin: ilki unrolling ile toplam (Bölüm 6), ikincisi kesirlerin toplamı (Bölüm 7), üçüncüsü bu bölümdeki tree.
Çözümü göster
- $T(n-1) + n$: size constant bir çarpanla küçülmüyor ($b$ yok). Unroll edince $n + (n-1) + \dots + 1 = \Theta(n^2)$.
- $T(n/5) + T(7n/10) + cn$: iki farklı size var, tek bir $a$ ve $b$ yok. Kesirler toplamı $9/10 < 1$ ⇒ $\Theta(n)$ (substitution ile $T(n) \le 10cn$).
- $2T(n/2) + n\log n$: $f = n\log n$, $n^d$ formunda değil; $d = 1$ çok küçük, $d = 1 + \epsilon$ çok büyük. Tree ile $\Theta(n\log^2 n)$.
- S20 örneği: $4T(n/2) + n^2/\log n$. $f$ ile $n^{\log_b a}$ arasında sadece $\log n$ çarpanı kadar fark var, polynomial bir fark yok.
CS161 Master theorem'i hangisine doğrudan uygulanabilir?
T(n−1) tipleri: unroll et ve topla
Size her adımda yarıya inmek yerine bir azalıyorsa tree'nin depth'i $\log n$ değil, $n$ olur. Tek call varsa tree bir zincirdir: her level'de bir node vardır ve kendi işi $f(k)$'dır. Toplam basitçe $f(n) + f(n-1) + \dots$.
Seç ve oynat. Fonksiyon $n = 8$ için gerçekten unroll ediliyor. Her satır bir level'deki call'ları ve onların işini sayıyor ($T(1) = 1$).
| Recurrence | Toplam | Θ |
|---|---|---|
| $T(n-1) + 1$ | $n$ | $\Theta(n)$ |
| $T(n-1) + n$ | $\frac{n(n+1)}{2}$ | $\Theta(n^2)$ |
| $T(n-1) + n^2$ | $\frac{n(n+1)(2n+1)}{6}$ | $\Theta(n^3)$ |
| $T(n-1) + \log n$ | $\log(n!)$ | $\Theta(n\log n)$ |
| $2T(n-1) + 1$ | $1 + 2 + 4 + \dots + 2^{n-1} = 2^n - 1$ | $\Theta(2^n)$ |
Select ya da QuickSort her seferinde minimum'u pivot seçerse subproblem size'ı $n-1$ olur: $T(n) = T(n-1) + cn$. Upper bound: $\sum_{k\le n} ck \le cn^2$. Lower bound: son $n/2$ term'in her biri $\ge cn/2$, toplam $\ge cn^2/4$. Yani $\Theta(n^2)$.
- $T(n-1)$'i "$b = \frac{n}{n-1}$" diye Master'a sokma: $b$ constant olmalı.
- $2T(n-1) + 1$ linear değil: call sayısı her level'de iki katına çıkıyor ve $n$ level var.
- $T(n-1) + n^2$ için "$n$ level × $n^2$" upper bound'u doğru ($O(n^3)$), ama Θ için lower bound'u da göster: son yarıdaki term'ler $\ge n^2/4$.
"For each of the questions below, please give the answer in terms of theta notation. (e) Solution to the recurrence $T(n) = T(n - 1) + 1$" (sorunun bu bölümle ilgili kısmı)
İpucu 1
Üç kez unroll et: $T(n) = T(n-1) + 1 = T(n-2) + 2 = T(n-3) + 3$. $k$ adım sonra ne olur?
İpucu 2
$T(1)$'e ulaşmak için kaç adım gerekiyor? Base case'in değeri constant.
Çözümü göster
$T(n) = T(n-1) + 1 = T(n-2) + 2 = \dots = T(n-k) + k$.
$k = n - 1$ alınca $T(n) = T(1) + n - 1$. $T(1)$ bir constant olduğu için $T(n) = \boxed{\Theta(n)}$.
Tree resmiyle: tek call olduğu için tree $n$ node'luk bir zincir, her node 1 iş yapıyor.
"For each recurrence, choose the expression (1)-(5) below which most accurately describes it. […] If it helps, $\log_2(3) \approx 1.6$, and $\sum_{i=0}^{t} i^2 = \theta(t^3)$. Assume that $T(1) = O(1)$ […]
(1) $\theta(\log n)$ (2) $\theta(n)$ (3) $\theta(n\log n)$ (4) $\theta(n^{\log_2 3})$ (5) $\theta(n^3)$
- $T(n) = T(n - 1) + n^2$"
(sorunun bu bölümle ilgili kısmı; tamamı Bölüm 4'te)
İpucu 1
Unroll et: her adımda size bir azalıyor ve o adımın işi $k^2$. Toplam hangi seri?
İpucu 2
Soruda verilen $\sum_{i=0}^{t} i^2 = \theta(t^3)$ tam olarak bu toplam, $t = n$ ile.
Çözümü göster
$T(n) = T(n-1) + n^2 = T(n-2) + (n-1)^2 + n^2 = \dots = T(1) + \sum_{k=2}^{n} k^2$.
$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6} = \Theta(n^3)$, $T(1) = O(1)$ ⇒ $T(n) = \Theta(n^3)$ ⇒ (5).
Master theorem burada uygulanmaz: size bölünmüyor, birer birer azalıyor. Lower bound'u merak edersen: son $n/2$ term'in her biri $\ge n^2/4$, toplam $\ge n^3/8$.
Kontrol: $T(1) = 1$ ile $T(n) = \frac{n(n+1)(2n+1)}{6}$; $n = 1000$'de $T(n)/n^3 \approx 0.334$, $\tfrac13$'e yaklaşıyor.
$T(n) = T(n-1) + \log n$ nedir?
Unequal split: kesirlerin toplamı
$T(n) = T(n/4) + T(n/2) + n^2$. Root $n^2$. Level 1: $(n/4)^2 + (n/2)^2 = \tfrac{5}{16}n^2$. Level 2: $(\tfrac5{16})^2 n^2$. Her level bir öncekinin $\tfrac5{16}$'sı kadar: geometric, root baskın, $\Theta(n^2)$.
Seç ve oynat. Tree gerçekten açılıyor (size'lar $n$'in kesri olarak yazılıyor). Her satırdaki toplam node'lardan hesaplanıyor.
$T(n) = \sum_i T(\alpha_i n) + c\,n^d$ için $s = \sum_i \alpha_i^d$ olsun. Level $t$'nin işi en fazla $c\,n^d s^t$.
- $s < 1$: geometric olarak azalır ⇒ $T(n) \le \frac{c\,n^d}{1-s}$ ⇒ $\Theta(n^d)$.
- $s = 1$: dolu level'ler $\approx c\,n^d$, depth $\Theta(\log n)$ ⇒ $\Theta(n^d\log n)$.
- $s > 1$: level'ler büyür, sonuç $n^d$'den büyük (Akra-Bazzi, 2025-26 s.46).
Aynı term'den birden fazla varsa katsayıyı da hesaba kat: $2T(n/2)$'nin katkısı $2 \cdot (1/2)^d$.
| Recurrence | $s$ | Sonuç | Nereden |
|---|---|---|---|
| $T(n/4) + T(n/2) + n^2$ | $\tfrac1{16} + \tfrac14 = \tfrac5{16}$ | $\Theta(n^2)$, $\le \tfrac{16}{11}n^2$ | 2025-26 s.27–35 |
| $T(n/5) + T(7n/10) + n$ | $\tfrac9{10}$ | $\Theta(n)$, $\le 10n$ | Select · S5.5 |
| $T(n/2) + T(n/10) + T(n/20) + n$ | $0.65$ | $\Theta(n)$ | 2023-24 S3(b) |
| $T(n/3) + T(2n/3) + n$ | $1$ | $\Theta(n\log n)$ | class prep S3'ün eşi |
| $2T(n/2) + 3T(n/3) + n^2$ | $\tfrac24 + \tfrac39 = \tfrac56$ | $\Theta(n^2)$ | CS161 concept check S3 |
$T(n) = T(n/5) + T(7n/10) + cn$'nin $O(n)$ olduğunu ispatla. $d \ge 10c$ koşulu nereden geliyor? $\tfrac15 + \tfrac7{10} = \tfrac9{10}$ ne rol oynuyor? Kesirler $\tfrac15 + \tfrac45 = 1$ olursa, ya da 1'i geçerse ne olur?
İpucu 1
Inductive hypothesis: her $k < n$ için $T(k) \le dk$. Bunu sağ tarafa koy: $T(n) \le \frac{dn}{5} + \frac{7dn}{10} + cn$.
İpucu 2
Sağ taraf $\left(\tfrac{9d}{10} + c\right)n$. Bunun $\le dn$ olması için $d$ ne olmalı? Kesirler toplamı 1 olunca aynı hesapta ne kalıyor?
Çözümü göster
$T(n) \le \frac{dn}{5} + \frac{7dn}{10} + cn = \frac{9}{10}dn + cn \le dn \iff cn \le \frac{1}{10}dn \iff d \ge 10c$. Base case için $d$'yi ayrıca $T(\text{küçük})$ değerlerini kapsayacak kadar büyük seç (S5.5'te $c = 1$, $d = 10$: $\tfrac{10}5 k + \tfrac{70}{10} k + k = 10k$).
$\tfrac9{10}$'un rolü: her level en fazla bir öncekinin $\tfrac9{10}$'u kadar. Geriye $\tfrac1{10}$'luk bir "pay" kalıyor ve $cn$'yi bu pay karşılıyor.
Kesirler toplamı 1 ise ($\tfrac15 + \tfrac45$): $dn + cn \le dn$ hiçbir $d$ için doğru değil, $O(n)$ ispatı çöker. Tree'de her dolu level $cn$ iş yapar ve depth $\Theta(\log n)$ ⇒ $\Theta(n\log n)$. Toplam 1'den büyükse level'ler büyür ve sonuç superlinear olur.
"For each recurrence, choose the expression (1)-(5) below which most accurately describes it. […] Assume that $T(1) = O(1)$ and don't worry about floors and ceilings.
(1) $\theta(\log n)$ (2) $\theta(n)$ (3) $\theta(n\log n)$ (4) $\theta(n^{\log_2 3})$ (5) $\theta(n^3)$
- $T(n) = T(n/2) + T(n/10) + T(n/20) + n$"
(sorunun bu bölümle ilgili kısmı; tamamı Bölüm 4'te)
İpucu 1
Üç call var ama size'ları farklı, Master theorem doğrudan uygulanmaz. $d = 1$ için $s = \sum_i \alpha_i$'yi hesapla.
İpucu 2
$\tfrac12 + \tfrac1{10} + \tfrac1{20}$ 1'den küçük mü? Küçükse level'ler geometric olarak küçülür ve root baskın olur.
Çözümü göster
$s = \tfrac12 + \tfrac1{10} + \tfrac1{20} = \tfrac{10 + 2 + 1}{20} = \tfrac{13}{20} = 0.65 < 1$.
Level $t$'nin işi en fazla $0.65^t\, n$. Toplam $\le n \sum_{t \ge 0} 0.65^t = \frac{n}{0.35} \approx 2.86n$ ⇒ $O(n)$. Root tek başına $n$ iş yapıyor ⇒ $\Omega(n)$. Sonuç $\Theta(n)$ ⇒ (2).
Substitution ile de kısa: $T(k) \le ck$ varsayımıyla $T(n) \le 0.65cn + n \le cn \iff c \ge \tfrac{1}{0.35} = \tfrac{20}{7}$.
Kontrol: floor'larla python'da çalıştırınca $n = 10^7$'de $T(n)/n \approx 2.84$, sınır $20/7 \approx 2.86$'nın altında.
CS161 concept check: $T(n) = 2T(n/2) + 3T(n/3) + n^2$ için $O(n^2)$'yi substitution ile ispatlamak istiyoruz. Hangi guess işe yarar ve aralarında en tight olanı hangisidir?
Change of variables: √n'li recurrence'lar
$n = 65536 = 2^{16}$'dan başla, 2'ye inene kadar karekök al: $65536 \to 256 \to 16 \to 4 \to 2$. Dört adım. Exponent'e bak: $16 \to 8 \to 4 \to 2 \to 1$. Karekök exponent'i yarıya indiriyor, exponent de $\log n$. Adım sayısı $\log(\log n) = \log 16 = 4$.
- $n = 2^m$ yaz. Böylece $\sqrt n = 2^{m/2}$, $n^{1/4} = 2^{m/4}$, $\log n = m$.
- Yeni fonksiyon tanımla: $S(m) = T(2^m)$. O zaman $T(\sqrt n) = S(m/2)$.
- $S$ için çıkan recurrence'ı Master theorem ile çöz.
- Geri dön: $m$ yerine $\log n$ yaz.
| $T$ | $S(m) = T(2^m)$ | $S$ çözümü | $T$ çözümü | Nereden |
|---|---|---|---|---|
| $T(\sqrt n) + 1$ | $S(m/2) + 1$ | $\Theta(\log m)$ | $\Theta(\log\log n)$ | 2019-20 S2 |
| $T(n^{1/4}) + 1$ | $S(m/4) + 1$ | $\Theta(\log m)$ | $\Theta(\log\log n)$ | 2020-21 S3 |
| $T(\sqrt n) + \log n$ | $S(m/2) + m$ | $\Theta(m)$ | $\Theta(\log n)$ | 2023-24 S3(b) |
| $2T(\sqrt n) + \log n$ | $2S(m/2) + m$ | $\Theta(m\log m)$ | $\Theta(\log n\,\log\log n)$ | S2 §3 |
- Geri dönmeyi unutma: $S(m) = \Theta(\log m)$ ise cevap $\Theta(\log\log n)$, $\Theta(\log n)$ değil.
- Base case 2'de durur, 1'de değil: $\sqrt 1 = 1$, sonsuza kadar 1 kalır. Bu yüzden sorular $T(2) = 1$ veriyor.
- $T(n^{1/4})$ cevabı da $\Theta(\log\log n)$: $\log_4\log n = \tfrac12\log\log n$, constant çarpan.
"2. Solve recurrence asymptotically. $T(2) = 1$, $T(n) = T(n^{1/2}) + 1$, $n > 1$"
İpucu 1
Üç kez unroll et: $T(n) = T(n^{1/2}) + 1 = T(n^{1/4}) + 2 = T(n^{1/8}) + 3$. $k$ adım sonra?
İpucu 2
$n^{1/2^k} = 2$ olduğunda dur. İki tarafın log'unu al: $\frac{\log n}{2^k} = 1$.
Çözümü göster
Yol 1 (unrolling): $T(n) = T(n^{1/2^k}) + k$. $n^{1/2^k} = 2 \iff \frac{\log n}{2^k} = 1 \iff 2^k = \log n \iff k = \log\log n$. O zaman $T(n) = T(2) + \log\log n = 1 + \log\log n = \Theta(\log\log n)$.
Yol 2 (change of variables): $m = \log n$, $S(m) = T(2^m)$ ⇒ $S(m) = S(m/2) + 1$. $a = 1$, $b = 2$, $d = 0$, $a = b^d$ ⇒ $S(m) = \Theta(\log m)$ ⇒ $T(n) = \Theta(\log\log n)$.
Kontrol: $n = 65536$: $65536 \to 256 \to 16 \to 4 \to 2$, $T = 4 + 1 = 5 = \log\log n + 1$ ✓.
"$T(2) = 1$, $T(n) = T(n^{1/4}) + 1$. Solve this recurrence asymptotically. Show your work."
İpucu 1
Aynı kalıp: $k$ adım sonra $T(n^{1/4^k}) + k$.
İpucu 2
$\frac{\log n}{4^k} = 1$ ⇒ $k = \log_4\log n$. Log base'ini değiştirmek sadece constant bir çarpan getirir.
Çözümü göster
$T(n) = T(n^{1/4}) + 1 = T(n^{1/16}) + 2 = \dots = T(n^{1/4^k}) + k$. $n^{1/4^k} = 2 \iff 4^k = \log n \iff k = \log_4\log n = \tfrac12\log\log n$. $T(n) = 1 + \tfrac12\log\log n = \Theta(\log\log n)$.
Change of variables ile: $S(m) = S(m/4) + 1$, $a = 1 = 4^0$ ⇒ $\Theta(\log m) = \Theta(\log\log n)$.
Kontrol: $n = 2^{16}$: $65536 \to 16 \to 2$, $T = 3 = \tfrac12 \cdot 4 + 1$ ✓. Altungöz'ün cevaplı kâğıdındaki sonuç da $\Theta(\log\log n)$.
"For each recurrence, choose the expression (1)-(5) below which most accurately describes it. […] Assume that $T(1) = O(1)$ and don't worry about floors and ceilings.
(1) $\theta(\log n)$ (2) $\theta(n)$ (3) $\theta(n\log n)$ (4) $\theta(n^{\log_2 3})$ (5) $\theta(n^3)$
- $T(n) = T(n^{1/2}) + \log n$ (Hint: Define $S(n) = T(2^n)$ for all $n$. Then, $S(n) = T(2^n) = T(\sqrt{2^n}) + \log 2^n = T(2^{n/2}) + n = S(n/2) + n$. Use the Master Theorem.)"
(sorunun bu bölümle ilgili kısmı; tamamı Bölüm 4'te)
İpucu 1
Soru change of variables'ı kendisi yapmış: $S(n) = S(n/2) + n$. Bu recurrence'ta $a$, $b$, $d$ kaç?
İpucu 2
$S$'yi çözdükten sonra geri dön: $T(n) = S(\log n)$. Seçenekleri $T$ için veriyorlar, $S$ için değil.
Çözümü göster
Hint'teki $n$ aslında bizim $m = \log n$'imiz: $S(m) = T(2^m)$, $S(m) = S(m/2) + m$.
$a = 1$, $b = 2$, $d = 1$, $b^d = 2 > 1$ ⇒ root-heavy ⇒ $S(m) = \Theta(m)$.
Geri dön: $T(n) = S(\log n) = \Theta(\log n)$ ⇒ (1).
Sezgi: karekök alındıkça $\log n$ term'leri $\log n,\ \tfrac12\log n,\ \tfrac14\log n, \dots$ diye yarıya iniyor. Bu geometric bir toplam, ilk term baskın: $\le 2\log n$.
Kontrol: $T(2) = 1$ ve $n = 2^{2^k}$ için tam değer $T(n) = 2\log n - 1$.
$T(n) = T(\sqrt n) + \log n$, $T(2) = 1$. $S(m) = T(2^m)$ ile hangisi çıkar?
Sınav provası: tipini tanı
Bu sorunun beş recurrence'ı, her biri kendi yöntemini anlatan bölüme kondu: 1. ve 2. recurrence Bölüm 4'te (Master theorem), 3. Bölüm 6'da ($T(n-1)$), 4. Bölüm 7'de (unequal split), 5. Bölüm 8'de (change of variables). Sınavda beşi aynı kâğıtta, karışık sırayla gelir. Bu yüzden asıl beceri, her recurrence'a bakınca hangi yöntemi isteyeceğini tanımak. (3) $\Theta(n\log n)$ seçeneği hiçbirine uymuyor, çeldirici olarak konmuş.
Arkadaşın MergeSort'un array'i üçe bölen bir versiyonunu yazmış (MergesortThirds: her biri $n/3$ size'ında üç parça, ardından linear time'da merge) ve bunun asymptotically daha hızlı olduğunu söylüyor. Haklı mı?
İpucu 1
Recurrence: kaç call, hangi size, merge ne kadar sürüyor?
İpucu 2
$a$ ve $b^d$ yine eşit mi? Değişen sadece log'un base'i mi?
Çözümü göster
$T(n) = 3T(n/3) + O(n)$: $a = 3 = 3^1 = b^d$ ⇒ $\Theta(n\log n)$. Log'un base'i değişir, $\log_3 n$ çıkar ama $\log_3 n = \log_2 n / \log_2 3$, aradaki fark constant bir çarpan. Asymptotically daha hızlı değil.
- 2023-24 S3(b): beş recurrence, seçenekli (Bölüm 4, 6, 7, 8). S3(d): Allie ve Brandon, sözel tanımdan recurrence (Bölüm 4).
- 2019-20 S2 ve 2020-21 S3: $T(\sqrt n) + 1$, $T(n^{1/4}) + 1$ (Bölüm 8).
- 2019-20 çözüm seti (UNM CS362) S1(d), S1(e): $8T(n/2) + \sqrt n$ (Bölüm 4), $T(n-1) + 1$ (Bölüm 6).
- Pratik vize S2: "Hint: divide-and-conquer" ile average case'te $O(n)$ çalışan bir algoritma. Algoritmayı tasarladıktan sonra recurrence (expectation'da, iyi bir split ile) $T(n) = T(n/2) + O(n)$ biçiminde olur, Master theorem ile $O(n)$.
- Sample 1 S1 ve S4: local minimum ve Fragment 3; çözümü kendin yaz.
- HW2: 1.1, 1.2 (Bölüm 4), 3(a) (yukarıda), 4(b) $a^b$'yi $O(\log b)$ multiplication ile hesapla ($T(b) = T(b/2) + O(1)$), 5(f) quagga: $T(n) \le T(n/2) + n/2$ ⇒ $O(n)$.
Son kontrol
Kâğıt kalemle çöz, sonra cevaba bak.
Sadece $T(n) \le 2T(n/2) + n$ biliniyor. Ne söyleyebilirsin?
$T(n) = 2T(n/2) + n\log n$?
$T(n) = T(n/3) + T(n/2) + n$?
$T(n) = 2T(n-1) + 1$, $T(1) = 1$?
$T(n) = 8T(n/2) + n^3$?