What is the time complexity of this atrocious algorithm?

Question

This grew out of a discussion of deliberately bad algorithms; credit to benneh on the xkcd forums for the pseudocode algorithm, which I've translated to Python so you can actually run it:

def sort(list):
    if len(list) < 2:
        return list
    else:
        if list[0] <= minimum(list[1:]):
            return list[0:1] + sort(list[1:])
        else:
            return sort(list[1:] + list[0:1])

def minimum(list):
    return sort(list)[0]

I'm interested in working out the worst-case, best-case and average-case time complexity, but I've found myself insufficiently practiced to do so. I originally thought it would be O(n!), which would be equivalent to cycling through all possible permutations of the list, but because the results aren't even memoized I believe it's actually worse than that.

Mitigating that is the fact that not all of the recursive calls can possibly be worst-case, so I'm not even sure what the worst-case input is for the function overall.

However—even a sorted input of size 5 results in a total of 64 recursive calls, or $2^{n+1}$. This is best-case time complexity.

What is the worst case input for this algorithm, and what is the time complexity for worst case and average case?

Answer 1

We can write a recurrence relation for this procedure as follows. Let $T(n)$ be the worst-case time for running sort on a list of length $n$. When calling sort on a list of length $n$, we can have up to $n$ recursive calls which rotate the list to the left until its minimum reaches the first entry. Each such call involves an invocation of minimum, and so takes $T(n-1) + O(n)$. The final one descends to sorting a list of length $n-1$. In total, we get the recurrence $$ T(n) = n T(n-1) + O(n^2). $$ Opening this recurrence, we get $$ T(n) = O(n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n!) = O(n!). $$ (We get $O(n!)$ since the terms decrease very quickly from $n!$ to $n^2$, faster than a geometric series.)

Of course, without giving a matching lower bound, we don't know whether this analysis is tight.

Answer 2

I was not careful and assumed a standard implementation of minimum, not the one given in the question. Hence, the answer below solves a much simpler problem.

---

Intuition: The algorithm is Selection Sort with a weird way to select the minimum; it can take quadratic time. That is, the algorithm takes cubic time in the worst case.

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= cn + \begin{cases} T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $cn$ for the (dominant term) of the toll function, which covers minimum, head and tail, as well as the other operations. We'll see that the constant factor is relevant. The one in the anchor turns out not to be, though.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider the reversely sorted list. Given such a list with $n$ elements, we hit case two $n-1$ times; then the originally last element (the minimum) is in front and we hit case one. In this case, $\mathtt{xs}$ is a reversely sorted list again, so we can set up the following recurrence:

$\qquad\begin{align*} T'(\leq 1) &= d, \\ T'(n) &= n \cdot cn + T'(n-1). \end{align*}$

Solving this we get that

$\qquad T'(n) = cn^3 + d \in \Theta(n^3)$,

which implies that

$\qquad T_{\mathrm{WC}}(n) \in \Omega(n^3)$.

Since no list can cause case two hit more than $n-1$ times per removed ($n$th-largest) element, this bound is tight; $T_{\mathrm{WC}}(n) \in \Theta(n^3)$.

FWIW, not much changes if you consider the average case. The toll function will then be $c \cdot \operatorname{rank}(\mathtt{x}, \mathtt{x::xs})$. In the random permutation model, the expected rank of $\mathtt{x}$ is $\frac{n}{2}$, and the model applies recursively. That is, $c$ changes in expectation, but the $\Theta$-class does not change.

Answer 3

Following the structured method outlined in our reference question on this Broken Selection Sort, you arrive at something like this:

$\qquad\begin{align*} T(\mathtt{[] | [x]}) &= d, \\ T(\mathtt{x::xs}) &= c + \begin{cases} 2 \cdot T(\mathtt{xs}), & \mathtt{x = min(x::xs)}; \\ T(\mathtt{xs}) + T(\mathtt{xs@[x]}, &\text{else}. \end{cases} \end{align*}$

I assume some cost measure that is related to list operations. Note that I introduce $c$ for the toll function, which covers head and tail, as well as the other operations.

Now, in order to get a lower bound on the worst-case cost we can fix any input. Let us consider almost reversely sorted lists with $n$ elements, i.e.

$\qquad \mathtt{L(n,i) = [i, \dots, 1, n, \dots, i+1]}$.

The recurrence from above then becomes:

$\qquad\begin{align*} T'(\mathtt{L(\leq 1, \_)}) &= d, \\ T'(\mathtt{L(n,i)}) &= c + \begin{cases} 2 \cdot T'(\mathtt{L(n-1,n-1)}), & \mathtt{i} = 1; \\ T'(\mathtt{L(n-1,i-1)}) + T'(\mathtt{L(n,i-1)}), &\text{else}. \end{cases} \end{align*}$

We see that we can express this in $n$ and $i$ only:

$\qquad\begin{align*} T'(\leq 1,\_) &= d, \\ T'(n, 1) &= c+ 2 \cdot T'(n-1, n-1),\quad n \geq 2, \\ T'(n, i) &= c + T'(n-1,i-1) + T'(n, i-1)\qquad n \geq 2, 2 \leq i \leq n. \end{align*}$

So we have $T_{\mathrm{WC}}(n) \geq T'(n,n)$ (the running time on the reversely ordered list).

To do: solve the recurrence

Scribbles:

• $T'(n,n) = c(n-1) + \sum_{i=1}^{n-1} T'(i+1,i)$
  (by succesively unfolding the terms with smallest first parameter)

  Note: bounding summands from below by $T'(i,i)$ yields a useless $2^n$ lower bound.

---

I think that the index of the smallest element is indeed the crucial quantity here. That would imply the following.

• $\mathtt{L(n,n)}$ is indeed a worst-case instance.

  Intuition: There is no way you can enforce more rotations.

• Not much changes on the average, assuming the random permutation model. The rank of the minimum is $n/2$ in expectation, and removing the minimum maintains the distributive properties from one rotation phase to the next.