0
$\begingroup$

I need to find an upper limit for the runtime of $f(n)$.

f(n):
{
 g(n,1)
}

g(n,k):
{
 if n<=0 return;
 for(i=1; i<=n; i++)
 {
  print "I love data structures!";
  k++;
  g(n-1, k);
 }
 return;
}

I tried to think of it this way:

for(i=1; i<=n; i++) $\rightarrow (n+1)c_2$

g(n-1, k) $\rightarrow ng(n-1)$

$$f(n) = g(n,1) + c_f = c_1 + (n+1)c_2 + nc_3 + nc_4 + ng(n-1) + c_f$$

I am not sure about the recursion runtime analysis:

g(n-1,k) $\rightarrow ng(n-1)$

Thank you!

$\endgroup$
0
$\begingroup$

The recursion for $g$'s running time is $$T(n)=n(T(n-1)+1)$$ where $1$ is the (constant) work done from the print statement and incrementing $k$. $g(n-1,k)$ and the constant work are called $n$ times from the for loop. The recursion stops at $g(0,k)$ which has running time $T(0)=1$.

Solving this recursion on Mathematica (I suspect doing it by hand would involve induction or inspection) gave the result: $$T(n)=\Gamma(n+1)+en\Gamma(n,1)$$ The complexity of this is $$T(n)=O(\Gamma(n+1)+en\Gamma(n,1))$$ $$T(n)=O(n\Gamma(n,1))$$ Since $n$ is an integer, then we can reduce this to $$T(n)=O(n!)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.