###### tags: `ADA 3.2` `Recursion-Tree Method`

# ADA 3.2: Recursion-Tree Method

Textbook Chapter 4.4 - The recursion-tree method for solving recurrences

# Review

### Merge Sort
之前[ADA 2.4](https://hackmd.io/_NxRWjS7Rluv43teXdvTUg)有用過 (Merge Sort)

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


\* T(n): 處理size為N所耗費的時間

# Recursion-Tree Method 遞迴樹法
### Solving recurrence
* Substitution method(取代法)
* ***Recursion-Tree method(遞迴樹法)***
* Master method(套公式大法/大師法)

### Steps to solve
- **Expand** a recurrence into a tree (把樹給展開)
- **Sum up** the cost of all nodes as a good guess (加總)
- **Verify** the guess as in substitution method (驗證)

### Advantages
- Promote intuition
- Generate good guesses for the subtitution method
=> 比較直覺, 容易猜

# Recursion-Tree Example

### 舉例

#### $T(n)=2T(n/2) + cn$ (Merge Sort)

每層都是cn, 故只要求出樹高就知道總和
$2^h=n$
$=>k = log_2 n$

總和則為
$cn \cdot$ tree height
$=> cn \cdot log_2n$
$=> O(nlogn)$

$T(n)=T(n/4)+T(n/2)+cn^2$


#### $T(n)=T(n/4)+T(n/2)+cn^2$

$= (T(\frac{n}{4}/4)+T(\frac{n}{4}/2) +c(\frac{n}{4})^2) + (T(\frac{n}{2}/4)+T(\frac{n}{2}/2) +c(\frac{n}{2})^2) + cn^2$

$=...$

累加後為
$T(n)\le (1+\frac5{16}+(\frac5{16})^2+(\frac5{16})^3+...)cn^2$

$=\frac {(1-(\frac5{16})^n)}{1-\frac5{16}}cn^2$

$=\frac{16}{11}cn^2$

$=O(n^2)$

> 當子問題足夠小時(切割次數趨近無限), 可以以O(1)秒解掉
$(\frac5{16})^n = 0$就可以忽略

###

:::info
等比級數相加公式
💡$a_1=a, a_n=a\cdot r^{n-1}, S_n = \frac {a(1-r^n)}{1-r}$

*Proof*
$S_0 = a + ar + a\cdot r^2+a\cdot r^3+...+a\cdot r^{n-1} ... (1)$

兩邊同乘$r$
$r \cdot S_0 = ar + a\cdot r^2+a\cdot r^3+...+a\cdot r^{n-1} + a\cdot r^{n} ... (2)$

$(1)-(2)$
$(1-r) \cdot S_0 = a-a\cdot r^n$

$S_0 = \frac{a-a\cdot r^n}{(1-r)}$

$= \frac{a(1-r^n)}{(1-r)}$
:::

#### 簡單證明
當 $0 <= r <= 1$時