Complexity of a recursive function

Question

I have a recursive function, and I'm trying to figure out it's complexity. denote P(n) - the runtime of the function (when given the parameter n). I know that : P(n)=n+(n-1)*P(n-1) [p(1)=1]

How can I express P(n) without using P(...) ?

Answer 1

You can write it something like $P(1)-1 = 0$, $P(n+1)-1 = n (2 + P(n)-1)$.

Now let's define $Q(n)=\frac{P(n)-1}{2}$ and we have $Q(1) = 0$, $Q(n+1) = n (1 + Q(n))$.

Now Q(5) is something like

5 (1 + 4 (1 + 3 (1 + 2 (1 + 1 (1 + 0)))))

5 + 5 * 4 + 5 * 4 * 3 + 5 * 4 * 3 * 2 + ...

and that's clearly less than

6!

So you could prove that P(n) is O(n!) along these lines.

Answer 2

Note that

$$ P(n) = n + (n-1)^2 + (n-1)(n-2)^2 + (n-1)(n-2)(n-3)^2 + \dots $$

So

$$ P(n) = O(n + n^2 + n^3 + n^4 + \dots + n^n) = O(n^n)$$