#### 代换法解(Substitution method)upper bounds

1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
Example: T(n) = 4T(n/2) + n

``````Inductive hypothesis: T(k) ≤ c1k2 – c2k for k < n.
T(n) = 4T(n/2) + n
= 4(c1(n/2)2 – c2(n/2)) + n
= c1n2 – 2c2n + n
= c1n2 – c2n – (c2n – n)
≤ c1n2 – c2n if c2 ≥ 1.``````

#### 递归树法(Recursion-tree method)解upper bounds

Example: T(n) = T(n/4) + T(n/2) + n²

``````          = n² + T(n/4) + T(n/2)
= n² + (n/4)² + (n/2)² + T(n/16)² + T(n/8)² + T(n/8)² + T(n/4)²
= ...
= n²(1 + 5/16 + (5/16)² + (5/16)³ + ...)
= Θ(n²) // ignore consts
```text
#### 主方法(Master method)解upper bounds
T(n) = aT(n/b) + f(n), where a>=1, b>1, and f is asymptotically positive.
case1:
```text
Compare f(n) with nlogba:
f(n) = O(n^(logba–ε)) for some constant ε > 0.
• f(n) grows polynomially slower than nlogba(by an nε factor).
=> T(n) = Θ(n^(logba)).``````

case2:

``````f(n) = Θ(n^(logba)*lgn) for some constant k ≥ 0.
• f(n) and n(logba) grow at similar rates.
=> T(n) = Θ(n^(logba) lgn).``````

case3:

``````f(n) = Ω(n^(logba)+ε) for some constant ε > 0.
• f(n) grows polynomially faster than nlogba (by
an nε factor),
and f(n) satisfies the regularity condition that
af(n/b) ≤ cf(n) for some constant c < 1.
=> T(n) = Θ(f(n)).``````

Example1: T(n) = 4T(n/2) + n
n^(logba–1) = n, case1, Result: Θ(n^(logba))

Example2: T(n) = 4T(n/2) + n²
n^(logba) = n², case2, Result: Θ(n^(logba) * lgn)

Example3: T(n) = 4T(n/2) + n³
n^(logba+1) = n³, case3, Result: Θ(n³)