###### tags: `ADA 3.1` `Solving Recurrences` `Substitution Method`
# ADA 3.1: Solving Recurrences & Substitution Method 取代法

Textbook Chapter 4.3 - The substitution method for solving recurrences 課本 p.104
Textbook Chapter 4.4 - The recursion-tree method for solving recurrences 課本 p.109
Textbook Chapter 4.5 - The master method for solving recurrences 課本 p.114

# D&C Algorithm Time Complexity

- $T(n)$: running time for input size n
- $D(n)$: time of Divide for input size n
- $C(n)$: time of Combine for input size n
- a: number of subproblems
- n/b: size of each subproblem

$T(n)=\begin{cases}
O(1) &\text{if } n\le c\\
aT(n/b)+D(n)+C(n) &\text{otherwise }
\end{cases}$

---

# Solving Recurrences

1. Substitution method(取代法)
- Guess a bound and then prove by induction (怎麼猜是有策略的)
2. Recursion-Tree method(遞迴樹法)
- Expand the recurrence into a tree and sum up the cost
- 這個方法最直覺，但要把式子嚴謹地展開寫出來會非常的麻煩
3. Master method(套公式大法/大師法)
- Apply Master Theorem to a specific form of recurrences
- Useful simplification tricks
- Ignore floors, ceilings, boundary conditions (proof in Ch. 4.6)
- Assume base cases are constant (for small n)

---

# Substitution Mehtod

Textbook Chapter 4.3 - The substitution method for solving recurrences

## Review

- Time Complexity for Merge Sort
- Theorem

$T(n)=\begin{cases}
O(1) &\text{if } n=1\\
2T(n/2)+O(n) &\text{if } n\ge2
\end{cases}$→$T(n)=O(n\log n)$

- Proof
- There exists positive constant a,b s.t. $T(n)=\begin{cases}
O(1) &\text{if } n=1\\
2T(n/2)+O(n) &\text{if } n\ge2
\end{cases}$
- Use induction to prove $T(n) \le b \cdot n\log n + a\cdot n$ （會講怎麼知道要加後面這個an）
- n = 1 , trivial
- n > 1,

$T(n)\le 2T(n/2)+bn$

$\le 2[b \cdot \frac{n}{2}\log\frac{n}{2}+a\cdot \frac{n}{2}]+b\cdot n$

$=b\cdot n\log n-b\cdot n+a\cdot n+b\cdot n$

$=b\cdot n\log n+a\cdot n$

:::info
💡 這裡需要查一下對數運算 $\log_a \frac bc = \log_ab-\log_ac$
所以
$\le 2[b \cdot \frac{n}{2}\log\frac{n}{2}+a\cdot \frac{n}{2}]+b\cdot n$
$\le b\cdot n\log\frac{n}{2}+a\cdot n+b\cdot n$
$= b\cdot n(\log n-\log 2)+a\cdot n+b\cdot n$
$=b\cdot n\log n-b\cdot n+a\cdot n+b\cdot n$
$=b\cdot n\log n+a\cdot n$
:::

:::info
💡 Substitution method (取代法)
guess a bound and then prove by induction

:::

取代法流程： 猜 → 驗證 → 解決(沒辦法解決就重猜)

- Guess the form of the solution
- Verify by mathematical induction (數學歸納法)
- Solve constants to show that the solution works
- Prove O and $\Omega$ separately

## Example

$T(n)=\begin{cases}
O(1) &\text{if } n=1\\
4T(n/2)+O(n) &\text{if } n\ge2
\end{cases}$

- Proof
- $T(n) = O(n^3)$

There exists postive constant $n_0, c$ s.t. for all $n \ge n_0, T(n) \le cn^3$

- Use induction to find the constant $n_0, c$
- $n = 1$, trivial
- $n > 1$,

$T(n) \le 4T(n/2)+bn$

$\le 4c(n/2)^3 + bn$ inductive hypothesis

$=cn^3/2+bn$

$=cn^3-(cn^3/2 - bn)$

:::info
💡 $cn^3/2-bn > 0$
e.g. $c \ge 2b, n \ge 1$

:::

$\le cn^3$

- $T(n)\le cn^3$ holds when $c = 2b, n_0 = 1$

上面的例子太鬆了找一個再緊一點的試試看

- Proof
- $T(n) = O(n^2)$

There exists postive constant $n_0, c$ s.t. for all $n\ge n_0, T(n) \le cn^2$

- Use induction to find the constant $n_0, c$
- $n = 1$, trivial
- $n > 1$,

$T(n)\le 4T(n/2)+bn$

$\le 4c(n/2)^2+bn$ inductive hypothesis

$=cn^2+bn$

:::info
💡 證不出來…
猜錯了？還是推導錯了？

:::

:::info
💡 沒猜錯，推導也沒有錯
這次取代法的小盲點

:::

所以策略就是，希望在計算的過程中生出一個負的東西可以把 bn 消掉

- Proof
- $T(n) = O(n^2)$

There exists postive constant $n_0, c_1, c_2$ s.t. for all $n\ge n_0, T(n) \le c_1n^2-c_2n$

:::info
💡 Strengthen the induction hypothesis by substracting a low-order term

:::

- Use induction to find the constant $n_0, c_1, c_2$
- $n=1, T(1)\le c_1-c_2$ holds for $c_1\ge c_2+1$
- $n > 1$,

$T(n)\le 4T(n/2)+bn$

$\le 4[c_1(n/2)^2-c_2(n/2)]+bn$ inductive hypothesis

$=c_1n^2-2c_2n+bn$

$=c_1n^2-c_2n-(c_2n-bn)$

:::info
💡 $c_2n-bn\ge0$
e.g. $c_2\ge b, n \ge 0$

:::

$\le c_1n^2-c_2n$

- $T(n)\le c_1n^2 - c_2n$ holds when $c_1 = b+1, c_2 = b, n_0 = 0$

## Useful Tricks

- Guess based on seen recurrences
- Use the recursion-tree method
- From loose bound to tight bound
- Strengthen the inductive hypothesis by subtracting a low-order term
- Change variables
- E.g., $T(n)=2T(\sqrt{n})+\log n$
1. Change vairable: $k = \log n, n = 2^k$ → $T(2^k)=2T(2^{k/2})+k$
2. Change variable again: $S(k)=T(2^k)$ → $S(k)=2S(k/2)+k$
3. Solve recurrence $S(k)=\Theta(k\log k)$ → $T(2^k) = \Theta(k\log k)$ → $T(n) = \Theta(\log n\log\log n)$