###### tags: `ADA 3.3` `Master Method`

# ADA 3.3: Master Method 大師套公式法

Textbook Chapter 4.5 - The master method for solving recurrences

# Master Theorem

The proof is in Ch. 4.6 課本 p.118

divide a problem of size n into a subproblems, each of size $\frac nb$ is solved in time $T(\frac nb)$ recursively

Let $T(n)$ be a positive function satisfying the following recurrence relation

$T(n)=\begin{cases}
O(1) &\text{if } n\le 1\\
a\cdot T(\frac nb)+f(n) &\text{if } n > 1,
\end{cases}$

符合上面的格式，就可以套用公式

where $a \ge 1$ and $b > 1$ are constants.

- Case 1: If $f(n)=O(n^{\log_b{a-\epsilon}})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_ba})$.
- Case 2: If $f(n)=\Theta(n^{\log_ba})$, then $T(n)=\Theta(n^{\log_ba}\cdot \log n)$.
- Case 3: If
- $f(n)=\Omega(n^{\log_b{a+\epsilon}})$ for some constant $\epsilon > 0$, and
- $a\cdot f(\frac nb)\le c\cdot f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.

:::info
💡 Compare $f(n)$ with $n^{\log_ba}$

:::

## Recursion-Tree for Master Theorem

$T(n) = aT(\frac nb)+f(n)$


### 複習一下數學
:::info
對數：$\log_2{2^3} = 3, \log_b{b^n} = n$

a 的次方數就是展開的層數，和b的次方的成長速度是一樣的，所以如果可以得到b的次方數的話就可以知道a的次方數

可以看到最後 $T(1)$ 時代表 n 就等於他的分母

例如：最後一層是 $b^3$ 好了那 a 的次方就可以這樣表示 $a^{\log_b{b^3}}=a^3$

只是我們不知道會展開幾層所以只能用 n 代替，所以這裡才會寫成 $a^{\log_bn} T(1)$
:::

## Recursion-Tree for Master Theorem(2)

回到之前的計算

$T(n)=f(n)+af(\frac nb)+a^2f(\frac n{b^2})+a^3f(\frac n{b^3})+...+a^{\log_bn}T(1)$

$a^{\log_bn}=n^{\log_na\cdot \log_bn} = n^{\log_ba}$

$a^{\log_bn}T(1) = n^{log_ba}T(1)$

為什麼要換成 n 為底呢？因為 n 是我們的 problem size 用 n 為底的話比較好判斷，也就會跟上面三個 case 長得差不多了

### 複習一下數學(2)
:::info
1. $a^{\log_bn}$ 是怎麼變成 $n^{\log_na\cdot \log_bn}$的呢？
1. 需要的知識是對數律 $\log_a{(b^n)}=n(\log_ab)$ → 真數 n 次方 ，對數 n 倍
2. 還有 $3^{\log_34} = 4, n^{\log_na}=a$

知道這些之後就可以開始推導

$a^{\log_bn}=n^{\log_n{a^{log_bn}}}$ 再用對數律真數 n 次方 ，對數 n 倍

$=n^{\log_na\cdot\log_bn}$

2. $a^{\log_bn}$ 又是怎麼變成 $n^{\log_ba}$ 的呢？
1. 這裡老師就有解釋了使用換底公式 $\log_ab=\frac{\log_cb}{\log_ca}$

知道換底公式之後就可以再從上面的結果繼續推導

$n^{\log_na\cdot\log_bn}=n^{\frac {\log_ba}{\log_bn}\cdot \log_bn}$

$=n^{\log_ba}$
:::

## Three Case

- $T(n)=aT(\frac nb)+f(n)$
- $a\ge 1$, the number of subproblems
- $b > 1$, the factor by which the subproblem size decreases
- $f(n)=$ work to divide/combine subproblems

$T(n)=f(n)+af(\frac nb)+a^2f(\frac n{b^2})+a^3f(\frac n{b^3})+...+a^{\log_bn}T(1)$

- Compare $f(n)$ with $n^{\log_ba}$
1. Case 1: $f(n)$ grows polynomially slower then $n^{\log_ba}$
2. Case 2: $f(n)$ and $n^{\log_ba}$ grow at similar rate
3. Case 3: $f(n)$ grows polynomially faster then $n^{\log_ba}$

## Case 1: Total dominated by leaves

ex. $T(n)=9T(\frac n3)+n, T(1) = 1$


:::info
💡 $f(n)$ grows polynomially slower then $n^{\log_ba}$

:::

$T(n) = (1+\frac93+(\frac93)^2+...+(\frac93)^{\log_3n})n$

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

:::

$=\frac{(\frac93)^{1+\log_3n}-1}{3-1}n$

$=\frac{3n}2\cdot\frac{9^{\log_3n}}{3^{\log_3n}}-\frac12n$

$=\frac{3n}2\cdot\frac{n^{\log_39}}{n}-\frac12n$

:::info
💡 這裡的 $9^{\log_3n}$ 是如何變成 $n^{\log_39}$ 請參考上面的 [複習一下數學(2)](#複習一下數學(2))

:::

$=\Theta(n^{\log_39})=\Theta(n^2)$

- Case 1: If $f(n)=O(n^{\log_b{a-\epsilon}})$ for some constant $\epsilon > 0$, then $T(n)=\Theta(n^{\log_ba})$.

## Case 2: Total cost evenly distributed among levels

ex. $T(n)=T(\frac{2n}3)+1, T(1)=1$


$a=1,b=\frac32$帶入公式 $n^{\log_ba}$

:::info
💡 這裡需要知道的知識是 $\log_b1$ 是多少，這代表的意義是 b 的幾次方是 1，我們知道 0 次方會是 1

:::

$n^{\log_{\frac32}1}=n^0$

:::info
💡 $f(n)$ and $n^{\log_ba}$ grow at similar rates

:::

$T(n)=T(\frac{2n}3)+1, T(1)=1$

$T(n)= 1+1+1+...+1$

$=\log_{\frac32}n+1$

$=\Theta(\log n)$

- Case 2: If $f(n)=\Theta(n^{\log_ba})$, then $T(n)=\Theta(n^{\log_ba}\cdot \log n)$

## Case 3: Total cost dominated by root cost

ex. $T(n)=3T(\frac n4)+n^5, T(1) = 1$


:::info
💡 $f(n)$ grows polynomially faster then $n^{\log_ba}$

:::

$T(n) = 3T(\frac n4)+n^5, T(1)=1$

$T(n)=(1+\frac3
{4^5}+(\frac3{4^5})^2+...+(\frac 3{4^5})^{\log_4n})n^5$

$T(n)>n^5$

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

:::

$T(n)\le \frac1{1-\frac3{4^5}}n^5$

:::info
💡 其中的 $(\frac 3{4^5})^{\log_4n}$應該是太小被省略了

:::

$T(n)=\Theta(n^5)$

- Case 3: If
- $f(n)=\Omega(n^{\log_b{a+\epsilon}})$ for some constant $\epsilon > 0$, and
- $a\cdot f(\frac nb)\le c\cdot f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.

## Example

:::info
💡 compare $f(n)$ with $n^{\log_ba}$

:::

- Case 1: If $T(n) = 9\cdot T(n/3)+n$, then $T(n)=\Theta(n^2)$

Observe that $n=O(n^2)=O(n^{\log_39})$

- Case 2: If $T(n)=T(2n/3)+1$, then $T(n)=\Theta(\log n)$

Observe that $1=\Theta(n^0)=\Theta(n^{\log_{3/2}1})$

- Case 3: If $T(n) = 3\cdot T(n/4)+n^5$, then $T(n)=\Theta(n^5)$
- $n^5=\Omega(n^{\log_4{3+\epsilon}})$ with $\epsilon=0.00001$
- $3(\frac n4)^5\le cn^5$ with $c=0.99999$

# Floors and Ceilings

- Master theorem can be extended to recurrences with floors and ceilings
- The proof is in the Ch. 4.6

$T(n)=aT(\lceil\frac nb\rceil)+f(n)$

$T(n)=aT(\lfloor\frac nb\rfloor)+f(n)$

# Theorem 1

試著用 Master method 套用到之前的 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) = O(n\log n)$

- Case 2

$f(n)=\Theta(n)=\Theta(n^1)=\Theta(n^{\log_22})=\Theta(n^{\log_ba})$

$T(n)=\Theta(f(n)\log n)=O(n\log n)$

# Theorem 2

試著用 Master method 套用到之前的 Bitonic Champion Problem

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

- Case 1

$f(n)=O(1)=O(n)=O(n^{\log_22})=O(n^{\log_ba})$

$T(n)=\Theta(n^{\log_22})=\Theta(n)$

# Theorem 3

試著用 Master method 套用到之前的改進的 Bitonic Champion Problem

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

$f(n)=\Theta(1)=\Theta(n^0)=\Theta(n^{\log_21})=\Theta(n^{\log_ba})$

$T(n)=\Theta(f(n)\log n)=O(\log n)$

---

###### Andy結論
:::warning
需要注意的是, 不論大 O 記法還是大 Θ 記法還是大 Ω 記法, 默認討論的都是最壞情況, 並不是像很多高票答主說的那樣, 大 Ω 記法就是討論最好情況了. 它們三個描述的都是同一個估計值 (比如某算法的最壞時間複雜度), 只是 O 描述這個估計值的上限, Ω 描述這個估計值的下限, 而 Θ 描述的是這個估計值的上限和下限相同 (即很確定了, 就在這一階了).
:::

:::warning
:::