Time Complexity Calculation - Is my approach correct?

55 Views Asked by At

Give the running time in terms of n.

 public static void spacejam(int n) {
         if (n <= 1) {
             return;
             for (int i = 0; i < n; i += 1) {
                 spacejam(n - 1);
             }
         }

My cost function is calls to spacejam. For n = 4, first there is 1 spacejam(4) call, then there are 4 spacejam(3) calls then 4.3 spacejam(2) calls and finally 4.3.2 spacejam(1) call.

current-call work (# of calls made)     i

spacejam(4) 4!/3!                       4

spacejam(3) 4!/2!                       3

spacejam(2) 4!/1!                       2

spacejam(1) 0                           1

Generalizing: runtime = total work = $\sum_{i=2}^n \dfrac{n!}{(i-1)!} \le n!(1 + \sum_{i=3}^n\dfrac{1}{(i-1)(i-2)}) = n!(2 - \dfrac{1}{n-1}) = O(n!)$

The answer derived in the solution is $O(n*n!)$ (additional n in multiplication) which agrees with my answer $O(n!)$ but I am not sure if that is correct. Could someone verify?