1
$\begingroup$

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

  • 0
    http://oeis.org/search?q=1%2C+3%2C+9%2C31%2C+129&language=english&go=Search2011-12-30

1 Answers 1

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.