Recurrences

알고리즘이 재귀적인 함수 호출을 사용하는 경우, 그것의 running time은 recurrence 형태로 설명될 수 있다.

Recurrence는 더 작은 크기의 입력을 가진 함수로 원래의 함수를 설명하는 것이다.

Solving recurrences

Asymptotic bounds를 사용한다.

The substitution method

1. Form a recursive form.
2. Guess the solution
3. Use mathemetical induction to prove the guess is right

Example1

Determining an upper bound on the recurrence
$T(n) = 2T(\lfloor n/2 \rfloor) + n$

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

Prove:
$T(n) \leq cn \log n$ (c는 적절한 양수)

Mathematical induction

1. Basis or boundary conditions
2. Inductive step

Bounary conditions

1. Find $T(n) \le cnlogn$ for $n \ge n_0$
2. $T(n) \ge cnlogn$ for n = 1?
   • $T(1) = 1$ but $c1log1 = 0$
3. $n_0 = 2$, $T(2) = 4 \le C2log2$
   • $c \ge 2$ and $n_0 \ge 2$
4. T(3)에 대해서도 확인
   • (3) 과정에서 찾은 c의 범위가 옳지 않을 수도 있기 때문이다.
   • $T(3) = 2T(1) + 3 = 5 \le c3log3$
   • $T(3)$에 대해서도 $c \ge 2$가 성립한다.
5. T(2)와 T(3)에 대해서 성립함을 증명했으므로 나머지는 Inductive step에서 증명한다.

Inductive step of example1

Assume that this bound holds for $\lfloor n/2 \rfloor$ ,
$T(\lfloor n/2 \rfloor) \leq c \lfloor n/2 \rfloor \log(\lfloor n/2 \rfloor)$.

$T(n) = 2T(\lfloor n/2 \rfloor) + n \leq 2(c \lfloor n/2 \rfloor \log(\lfloor n/2 \rfloor)) + n$
$\leq c n \log(n/2) + n$
$= c n \log n - c n \log 2 + n$
$= c n \log n - c n + n$
$\leq c n \log n$
(as long as c $\ge$ 1)

The recursion-tree method

substitution method로 증명하기 전 guess 과정에서 좋은 solution을 얻기 위해 사용

example2

Find guess using recursion tree

$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$

$T(n) = \Theta(n^2)$임을 증명하자

1. Show $T(n) = \Omega(n^2)$

   • Obvious

2. Show $T(n) = O(n^2)$

   • Guess by the recursion-tree method
   • Prove by the substitution method

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

$n = 4^k$, $T(n) = cn^2$ 이라고 가정하면 위 그림처럼 된다.
맨 위의 root node의 depth는 0이다.

cost computation (cost를 이용해 $T(n) = O(n^2)$를 끌어내자)

Subproblem size for a node at depth i: $n/4^i$
The number of nodes at depth i: $3^i$
The number of levels: $log_4n +1$

cost of each depth

• except the last level: $3^ic(n/4i)^2= (3/16)^icn^2$
• The last level: $\theta(3^{\log_4{n}}) = \theta(n^{\log_4{3}})$

cost of all depths

$T(n) = \sum_{i=0}^{\log_4{n}-1} \left( \frac{3}{16} \right)^i cn^2 + \Theta(n^{\log_4{3}})$

$< \sum_{i=0}^{\infty} \left( \frac{3}{16} \right)^i cn^2 + \Theta(n^{\log_4{3}})$

$= \frac{1}{1 - (3/16)} cn^2 + \Theta(n^{\log_4{3}})$

$= \frac{16}{13} cn^2 + \Theta(n^{\log_4{3}})$

$= O(n^2)$

prove $T(n) = O(n^2)$ by the substitution method

Show that $T(n) \leq dn^2$ (for $d > 0$ and for the same $c > 0$)
Recursion tree 를 통해 $T(n) = \theta(n^2)$ 임을 증명했으므로 $T(n) = cn^2$ 으로 잡을 수 있다.

$T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$

$\leq 3d \lfloor n/4 \rfloor^2 + cn^2$

$\leq 3d(n/4)^2 + cn^2$

$= \frac{3}{16} dn^2 + cn^2$

$\leq dn^2$

where the last step holds as long as $d \geq \frac{16}{13}c$.

따라서 $T(n) = \Omega(n^2)$ 이자 $T(n) = O(n^2)$ 이므로, $T(n) = \theta(n^2)$ 이다.

example3

Given $T(n) = T(n/3) + T(2n/3) + O(n)$, to show $T(n) = O(nlgn)$

recursion tree

위 그림의 tree의 최대 높이는 $log_\frac{3}{2}n$ 이다.

cost computation

the cost of each level: $cn$

height
$n → (2/3)n → (2/3)2n → ··· → 1=> \frac{2}{3}kn = 1$
when $k = log_\frac{3}{2}n,=> log_\frac{3}{2}n$

Total : each level cost x height
$O(cnlog_\frac{3}{2}n) = O(nlogn)$

substitution method of $T(n) = O(nlogn)$

$T(n) \leq T(n/3) + T(2n/3) + cn$

$\leq d(n/3)\log(n/3) + d(2n/3)\log(2n/3) + cn$

$= \left( d(n/3)\log n - d(n/3)\log 3 \right) + \left( d(2n/3)\log n + d(2n/3)\log(2/3) \right) + cn$

$= dn \log n + d\left( -(n/3)\log 3 + (2n/3)\log(2/3) \right) + cn$

$= dn \log n + d\left( -(n/3)\log 3 + (2n/3)\log 2 - (2n/3)\log 3 \right) + cn$

$= d n \log n + d n(-\log 3 + 2/3) + cn$

$\leq d n \log n, \quad \text{as long as} \quad d \geq \frac{c}{\log 3 - 2/3}$