Solve the recurrence relation $T(n) = (n-1) T(n-1)$

Question

How do I resolve the following recurrence relation?

• $T(n) = (n-1) T(n-1),$

• $T(1) = 1.$

My reasoning:

$T(n) = T(n-1-k)(n-1)(n-2)(n-3)\cdots(n-k)$

$k = n$ $\leftarrow$ yields the base case

$T(n) = T(1)\cdot n!$
$T(n) = n!$

In terms of Big O complexity, this would be:

$T(n) = O(n!)$

This question, inspired from:

https://stackoverflow.com/questions/52710864/what-is-the-time-complexity-of-this-5-line-java-algorithm

claims the answer is double factorial: $O(n) = n!!$

How so?

Answer 1

You can use Stirling's approximation

$n!=nlogn - n$

to show that

$n!=n^n*1/e^n$

So, $n!=O(n^n)$