Can a Minimum Possible Efficiency be proven?

Question

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of $O(n^2)$ such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have $O(n \log n)$, which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently than $\Theta(n\log n)$. Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?

Answer 1

There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory.

An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to discover precisely which permutation it is.

To transmit a number between $1$ and $m$ requires transmitting $\log_2 m$ bits of information. To transmit a permutation of $n$ elements, therefore, requires $\log_2 n!$ bits of information. By Stirling's approximation, this turns out to be $n \log_2 n + O(\hbox{low order})$ bits.

A binary comparison operation discovers one bit of information. It follows that any sorting algorithm which only uses a binary comparison operation must perform at least $n \log_2 n + o(n \log n)$ comparisons. If we assume that a comparison takes a constant amount of time, that means that the sort must take at least $\Omega(n \log n)$ time.

A radix sort could beat this by discovering more than one bit of information per query.

A similar argument shows that binary search is optimal. You are trying to find a number between $1$ and $n$, which means discovering $\log_2 n$ bits of information. If your query operation returns one bit of information, you need at least $\log_2 n$ queries to find an element.

It's a similar story with space usage. Suppose that you need to store a permutation in memory. By an identical argument, this requires at least $n \log_2 n + o(n \log n)$ bits of storage. Since you need $\log_2 n$ bits to store an integer between $1$ and $n$, you essentially can't do any better than storing $n$ integers.

Answer 2

Sorting, in fact, has been proven to take at least $O(n \log n)$ time if the sort is based on comparisons. For integers of fixed size, there are faster methods (radix sort).

However, sorting is one of the rare problems where this has been done. In general, we don't know lower bounds for the time complexity of most problems. For example, if we know that $O(2^n)$ was a lower bound for $NP$-complete problems, then we'd know that $P \neq NP$. But no such result has been proven, so $P$ vs $NP$ remains a mystery.

For problems in general, there is no algorithm which can take in a representation of a problem and return a lower bound on its time complexity. This is because the set of such complexities would be an index set: that is, it represents a property of languages (problems), not of algorithms. There's a result called Rice's Theorem which says that any such sets are undecidable.

Answer 3

In general this is possible, but it is crucial you specify the model of computation when doing so. A classic example well-known is the $\Omega(n \log n)$ bound on sorting in the decision tree model. To circumvent the sorting lower bound proven in the decision tree model, you must not perform comparisons.

Another example is the cell probe model. In addition to the examples on Wikipedia, you can look at e.g. Fredman-Saks (STOC'89). This is a strong model; if you'd like to beat a bound with an algorithm, you must not access memory.