What's the time complexity of this function?
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 &lt; 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!)$.