Question

Cosider the following code
foo(int n)
{
int x = 0;
if (n == 1) return;
for (i=1; i<=n; ++i)
x + = foo (n-1);
return (x);
}

The worst case complexity of time is

• A. $O\left(2^n\right)$
• B. O(n)
• C. $O\left(n^2\right)$
• D. $O(n!)$

Answer 1

The correct option is D $O(n!)$

$T\left(n\right)=n\ast T(n-1)$

Which evaluates to O(n!)