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(...) ?
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(...) ?
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.