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!
Converting a algorithm to a runtime function
runtime analysis;recursion
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!)$$