###### tags: `ADA 3.1` `Recurrences` `Substitution Method` # Solving Recurrences

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

主要在解釋如何得到我們使用Divide and Conquer得出解後，如何得到時間複雜度。

## D&C Algorithm Time Complexity


- T(n): 要解決N個Case時所花的時間
- D(n): 需要Divide N個Case時所花的時間
- C(n): 需要Combine N個Case時所花的時間
- **a**: Dive後還有幾個`SubProblem`
- **n/b**: 每一個`SubProblem`的大小
- 如果是從中間切分開，a=b=2 -> `Size = n/2`
- **b 不一定 == a**
- Bitonic Champion Problem(2.5) 只需要看一邊 a=1 b=2 -> `Size = n/2`

---

#### 當Case足夠少的時候，複雜度 == O(1)
#### 其他情況， 複雜度 == `幾個SubProblem`*`每個SubProlem的大小` ＋ `Divide的時間` ＋`Combine 的時間`

---

## Solving Recurrences

1. 猜出一個Bound 藉由 Induction去證明
2. 畫出Recursion Tree -> 費時
3. ？？？？？

## Substitution Method

先從寬鬆一點的假設開始證明
---
透過假設 $T(n) = O(n^3)$
- 帶入for all $n \ge n_0, T(n) \le cn^3$
- 將hypothesis case帶入公式替換

往下假設去尋找tighter upper bound
---
- 同上的步驟 整理到 $T(n) =cn^2+bn$

`歸納法的盲點 沒有猜錯 推演過程也沒有錯 但是無法證成功`

在Hypothesis的過程加上一個low-order term的作法
---

Some Tricks
---