Consider the below function:
Considering that print(a) and swap(a, b) are of complexity $\theta(1)$, what is the time complexity of the above code?
The answer that comes to my mind is $\theta((n-k)!)$ or $\mathcal{O}(n!)$.
However in the book that I'm reading it says it's of order $\theta(n!)$. What am I missing here?
Denote the time complexity of $f$ on inputs $a,k,n$ by $T(k,n)$ (the time complexity doesn't depend on $a$ in your model). The time complexity satisfies the recurrence $$ T(k,n) = (n-k+1)T(k+1,n) + \Theta(n-k+1). $$ with base case $T(n,n) = \Theta(1)$. Define $$ S(k,n) = \frac{T(k,n)}{(n-k+1)!}. $$ Then $S(n,n) = \Theta(1)$ and for $k < n$, $$ S(k,n) = S(k+1,n) + \Theta\left(\frac{1}{(n-k)!}\right). $$ It follows that $$ S(k,n) = \Theta\left(\frac{1}{(n-k)!} + \cdots + \frac{1}{1!} + 1\right) = \Theta(1), $$ and so $T(k,n) = \Theta((n-k+1)!)$.
If you take $T(n) = \max_{1 \leq k \leq n} T(k,n)$, then indeed $T(n) = \Theta(n!)$.
