World's most popular travel blog for travel bloggers.

# Converting a algorithm to a runtime function

, ,
Problem Detail:

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!

###### Answered By : Victor Phan

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!)$$