1
$\begingroup$

Consider the below function: Function Code

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.