[알고리즘]Factorial

Factorial Problem

f(n) = n!
Def: $n! = 1*2*3*...*(n-1)$ , $for (n \ge 1)$, $0! = 1$

F(n)=n*F(n-1) for $n\ge1$; //recursive case
F(0)=1//terminae case

1. input size: n
2. basic operation = multiplication(*)
3. worst, best, average case를 체크한다.
4. recurrence 관계를 만든다.

step4

M(n) = M(n-1)+1 , M(0) = 0 //1! = 1, 0!=0

step5

backward substitution 정의에 따르면

M(n) = M(n-1)+1
M(n) = [M(n-2)+1]+1 = M(n-2)+2
M(n) = [M(n-3)+1]+1+1 = M(n-3)+3
....
M(n) = M(n-i)+i // i번째 call

M(n) = M(n-n)+n // n번째 콜
M(n) = M(0)+n=n

step6

simplification n-> $\infty$
M(n)$\in\theta(n)$