---
# System prepended metadata

title: 'ADA 3.2: Recursion-Tree Method'
tags: [ADA 3.2, Recursion-Tree Method]

---

###### 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}$

![](https://i.imgur.com/DYeIcun.png)

\* 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)
![](https://i.imgur.com/f9YnePw.png)

每層都是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$

![](https://i.imgur.com/tow3vxw.png)

#### $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$時

![](https://i.imgur.com/B9Y0qtB.png)
