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?