# Recursion trees Problem 2

Here is the definition of T for reference:
• T(1) = c
• T(n) = nT(n-1) + 1

### Solution

(a) The root node is at level 0. At level 1 are the n children of the root node. Each of these has n-1 children, so there are n(n-1) nodes at level 2. And then n(n-1)(n-2) nodes at level 3.

(b) The problem size at level k is n-k. The input at the base case is 1. So we need to solve n-k = 1. That is, the leaf level, i.e. the height of the tree, is n-1.

(c) Extrapolating the pattern we saw in part (a), there must be n! leaves in the tree. Each leaf contains the value c. So the sum of the values in the leaf nodes is cn!.

(d) The closed form for T will be the sum of the values in the leaf nodes plus the sum of the values in the internal nodes. The sum of all the leaf values is cn! and we know that n! grows faster than $$2^n$$. So the closed form cannot be $$O(2^n)$$.