[Solved]: What is the time complexity of this atrocious algorithm?

Problem Detail: 

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?

Asked By : Wildcard

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48482

 Ask a Question

 Download Related Notes/Documents