# What's the time complexity of this function?

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?

• I is obviously dependent on $k$. I would suspect your book has a mistake. I also think its $\Theta((n-k)!)$ Mar 15 at 13:47

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