对于n叉recursion tree，不管是BFS1或者DFS，如果每次recursion的time complexity都是O(1)，那么总的time complexity就转化成了计算node的总数。
对于二叉树，各层的节点数量依次为(n层)：1, 2, 4, …, 2^(n-2), 2^(n-1)。
总数可以这样计算：
1 + 2 + 4 + … + 2^(n-2) + 2^(n-1)
= 2^n(1/(2^n) + 1/(2^(n-1)) + … + 1/4 + 1/2))
= 2^n(1/2 + 1/4 + 1/8 + … + 1/(2^n))
~ 2^n
Time Complexity: O(2^n)
最后一层的Time Complexity为O(2^(n-1)) = O(2^n)
对于string permutation，假设有n个字符，最后一层和倒数第二层数量相同，于是只考虑到倒数第二层，那么各层节点数量依次为：
1, n, n(n-1), n(n-1)(n-2), …, n!
总数量可以这样计算：
1 + n + n(n-1) + n(n-1)(n-2) + … + n!
= n!(1/(n!) + 1/((n-1)!) + 1/((n-2)!) + … + 1/3! + 1/2! + 1)
= n!(1 + 1/2 + 1/6 + 1/24 + … + 1/n!)
< n!(1 + 1/2 + 1/4 + 1/8 + … + 1/(2^(n-1)))
= 2n!
Time Complexity: O(n!)
最后一层的Time Complexity也是O(n!)
那么是不是n叉树，即使dynamic changing也可以认为总时间复杂度和最底层的时间复杂度一样呢？
假设第i层的每个节点的分支数量为f(i)，最后一层的节点数量为t
第2层的节点数量为f(1)，第3层的节点数量为f(1)f(2)，第n-1层为f(1)f(2)…f(n-2)
第n层为t=f(1)f(2)…f(n-2)f(n-1)
可知f(1), f(2), …, f(n) >= 2, f(1)f(2)…f(n) >= 2^n
前n-1层的总和为：
1 + f(1) + f(1)f(2) + … + f(1)f(2)…f(n-2)
= t(1/(f(1)f(2)…f(n-1)) + 1/(f(1)f(2)…f(n-2)) + … + 1/(f(1)f(2)) + 1/(f(1)))
= t(1/(f(1)) + 1/(f(1)f(2)) + … + 1/(f(1)f(2)…f(n-2)) + 1/(f(1)f(2)…f(n-1)))
< t(1/2 + 1/4 + … + 1/(2^(n-2)) + 1/(2^(n-1)))
~ t
前n-1层的Time Complexity为O(t)
最后一层的Time Complexity为O(t)
总的Time Complexity: O(t) + O(t) = O(t)
Code Carpenter 