tags: ADA 3.1 Solving Recurrences Substitution Method

ADA 3.1: Solving Recurrences & Substitution Method 取代法

Textbook Chapter 4.3 - The substitution method for solving recurrences 課本 p.104
Textbook Chapter 4.4 - The recursion-tree method for solving recurrences 課本 p.109
Textbook Chapter 4.5 - The master method for solving recurrences 課本 p.114

D&C Algorithm Time Complexity

• $T(n)$: running time for input size n
• $D(n)$: time of Divide for input size n
• $C(n)$: time of Combine for input size n
• a: number of subproblems
• n/b: size of each subproblem

$T(n)=\{\begin{array}{ll}O(1)& \text{if }n\le c\\ aT(n/b)+D(n)+C(n)& \text{otherwise }\end{array}$

---

Solving Recurrences

1. Substitution method(取代法)
   • Guess a bound and then prove by induction (怎麼猜是有策略的)
2. Recursion-Tree method(遞迴樹法)
   • Expand the recurrence into a tree and sum up the cost
   • 這個方法最直覺，但要把式子嚴謹地展開寫出來會非常的麻煩
3. Master method(套公式大法/大師法)
   • Apply Master Theorem to a specific form of recurrences

• Useful simplification tricks
  • Ignore floors, ceilings, boundary conditions (proof in Ch. 4.6)
  • Assume base cases are constant (for small n)

---

Substitution Mehtod

Textbook Chapter 4.3 - The substitution method for solving recurrences

Review

• Time Complexity for Merge Sort
• Theorem

$T(n)=\{\begin{array}{ll}O(1)& \text{if }n=1\\ 2T(n/2)+O(n)& \text{if }n\ge 2\end{array}$→

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

• Proof

  • There exists positive constant a,b s.t.
    $T(n)=\{\begin{array}{ll}O(1)& \text{if }n=1\\ 2T(n/2)+O(n)& \text{if }n\ge 2\end{array}$
  • Use induction to prove
    $T(n)\le b\cdot n\log n+a\cdot n$ （會講怎麼知道要加後面這個an）

    • n = 1 , trivial

    • n > 1,

      $T(n)\le 2T(n/2)+bn$
      $\le 2[b\cdot \frac{n}{2}\log \frac{n}{2}+a\cdot \frac{n}{2}]+b\cdot n$
      $=b\cdot n\log n-b\cdot n+a\cdot n+b\cdot n$
      $=b\cdot n\log n+a\cdot n$

      💡 這裡需要查一下對數運算

      ${\log }_a\frac{b}{c}={\log }_{a}b-{\log }_{a}c$
      所以
      

      $\le 2[b\cdot \frac{n}{2}\log \frac{n}{2}+a\cdot \frac{n}{2}]+b\cdot n$
      

      $\le b\cdot n\log \frac{n}{2}+a\cdot n+b\cdot n$
      

      $=b\cdot n(\log n-\log 2)+a\cdot n+b\cdot n$
      

      $=b\cdot n\log n-b\cdot n+a\cdot n+b\cdot n$
      

      $=b\cdot n\log n+a\cdot n$

  💡 Substitution method (取代法)
  guess a bound and then prove by induction

取代法流程： 猜 → 驗證 → 解決(沒辦法解決就重猜)

• Guess the form of the solution
• Verify by mathematical induction (數學歸納法)
• Solve constants to show that the solution works
• Prove O and
  $\mathrm{\Omega }$ separately

Example

$T(n)=\{\begin{array}{ll}O(1)& \text{if }n=1\\ 4T(n/2)+O(n)& \text{if }n\ge 2\end{array}$

• Proof

  • $T(n)=O(n^3)$

    There exists postive constant

    $n_0,c$ s.t. for all
    $n\ge n_0,T(n)\le c{n}^3$

  • Use induction to find the constant

    $n_0,c$
    • $n=1$, trivial
    • $n>1$,
    $T(n)\le 4T(n/2)+bn$
    $\le 4c(n/2{)}^3+bn$ inductive hypothesis
    $=c{n}^3/2+bn$
    $=c{n}^3-(c{n}^3/2-bn)$

    💡

    $c{n}^3/2-bn>0$
    e.g.

    $c\ge 2b,n\ge 1$

    $\le c{n}^3$

  • $T(n)\le c{n}^3$ holds when
    $c=2b,n_0=1$

上面的例子太鬆了找一個再緊一點的試試看

• Proof

  • $T(n)=O(n^2)$

    There exists postive constant

    $n_0,c$ s.t. for all
    $n\ge n_0,T(n)\le c{n}^2$

  • Use induction to find the constant

    $n_0,c$
    • $n=1$, trivial
    • $n>1$,
    $T(n)\le 4T(n/2)+bn$
    $\le 4c(n/2{)}^2+bn$ inductive hypothesis
    $=c{n}^2+bn$

    💡 證不出來…
    猜錯了？還是推導錯了？

    💡 沒猜錯，推導也沒有錯
    這次取代法的小盲點

所以策略就是，希望在計算的過程中生出一個負的東西可以把 bn 消掉

• Proof

  • $T(n)=O(n^2)$

    There exists postive constant

    $n_0,c_1,c_2$ s.t. for all
    $n\ge n_0,T(n)\le c_1{n}^2-c_{2}n$

    💡 Strengthen the induction hypothesis by substracting a low-order term

  • Use induction to find the constant

    $n_0,c_1,c_2$

    • $n=1,T(1)\le c_1-c_2$ holds for
      $c_1\ge c_2+1$

    • $n>1$,
      $T(n)\le 4T(n/2)+bn$
      $\le 4[c_1(n/2{)}^2-c_2(n/2)]+bn$ inductive hypothesis
      $=c_1{n}^2-2c_{2}n+bn$
      $=c_1{n}^2-c_{2}n-(c_{2}n-bn)$

      💡

      $c_{2}n-bn\ge 0$
      e.g.

      $c_2\ge b,n\ge 0$

      $\le c_1{n}^2-c_{2}n$

  • $T(n)\le c_1{n}^2-c_{2}n$ holds when
    $c_1=b+1,c_2=b,n_0=0$

Useful Tricks

• Guess based on seen recurrences
• Use the recursion-tree method
• From loose bound to tight bound
• Strengthen the inductive hypothesis by subtracting a low-order term
• Change variables
  • E.g.,
    $T(n)=2T(\sqrt{n})+\log n$
  1. Change vairable:
     $k=\log n,n=2^k$ →
     $T(2^k)=2T(2^{k/2})+k$
  2. Change variable again:
     $S(k)=T(2^k)$ →
     $S(k)=2S(k/2)+k$
  3. Solve recurrence
     $S(k)=\mathrm{\Theta }(k\log k)$ →
     $T(2^k)=\mathrm{\Theta }(k\log k)$ →
     $T(n)=\mathrm{\Theta }(\log n\log \log n)$