Solving recurrences

: 러닝타임 식에 자기 자신이 또들어잇을 수 잇음  recursive~

-> 푸는 방법 (guess->증명 으로 푸는데, guess시에는 2쓰고 증명에는 1쓴다)

1. substitution method  

2. recursion-tree method 

3. master methond

-> 목표 : Θ / O bound를 찾는 것

 

substitution methond

1. solution을 guess한다 (- guess할 때 recursion-tree method 사용함)

2. mathematical method (수학적 귀납법)으로 추측이 맞는지 증명한다

- basic or boundary condition 이 true인지 보여준다

- inductive step~ (n=어떨 때 성립한다고 가정 -> n일때 성립함을 보여준다)

ex)

 

recursion-tree method

:good solution 을 guess할 때 사용

각 level에서의 합과 깊이를 구해 곱해서 total 합을 구함