Recurrence Equation

expression

• T(n)
  • n=1; c
  • n>1; 2T(n/2) + c*n
• Recurrence; 점화식
  • Floor and ceilings
  • Exact vs. asymptotic functions
  • Boundary conditions (base casse로 보내는 것)

Solving Recurrence Equations

1. Substitution method
   • 어느 정도 solution이 맞다는 것을 증명하는 방법
2. Recursion-tree method
   • 트리를 그려서 답을 도출하는 방법
3. Iteration method
   • 1씩 줄어드는 기법, divide&conquer에서는 많이 사용X(점화식)
4. Master method
   • 대입법

Substitution method

• mathematical induction

1. base case

2. inductive hypothesis

3. 결론

example1.

• T(n)
  • n=1; theta(1)
  • n>1; 2T(n/2) + n
• T(n) = O(nlgn)이라고 가정하자.
  • 몇몇 c>0에 대하여 T(n) ≤ cnlgn 이 만족함을 증명하자.

    • T(n) = 2T(n/2) + n