# 用主定理解阶乘递归算法的复杂度

## 主定理的适用范围

Master theorem applies only to the divide and conquer type recurrences, like T(n) = a*T(n/b) + f(n) where a is the number of subproblems and each of these subproblem's size is 1/b of the original problem. But recurrence T(n) = T(n-1) + 2 does not technically "divide" the problem into subproblems. so master theorem does not apply here[2]https://stackoverflow.com/questions/3224240/recurrence-relation-solving-big-o-of-tn-1.

## 正确的方法

$$T(n) + T(n-1) + T(n-2) + ... + T(1) = T(n-1) + T(n-2) + ... + T(0) + \sum_{1}^{n} 1$$

$$T(n) = n + T(0)$$

↑1 https://blog.csdn.net/weixin_38233103/article/details/110592111 https://stackoverflow.com/questions/3224240/recurrence-relation-solving-big-o-of-tn-1