# What are some problems where we know we have an optimal algorithm?

What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)

And how is this proved?

• A turing machine is a tricky model for lower bounds. Changing the defn can change the polynomial in the running time, so you need to be a little more specific. – Suresh Venkat Jan 22 '12 at 2:13
• How do you define non-trivial? – funkstar Jan 24 '12 at 8:03
• As says Suresh, the kind of TM you use has an influence. I guess that for the language of palindromes (words you can read backwards), we have an optimal 1-tape TM which takes $\mathcal O(n^2)$ steps to decide the language. And for 2-tape TMs, it is decidable in linear time, thus pretty much optimal too. – Bruno Jun 27 '12 at 6:41
• – BlueRaja - Danny Pflughoeft Jun 27 '12 at 21:26

Any algorithm which takes linear time and has to read its whole input must be asymptotically optimal. Similarly, as Raphael comments, any algorithm whose runtime is of the same order as output size is optimal.

• Similarly, any algorithm whose runtime is of the same order as output size is optimal. – Raphael Jan 21 '12 at 16:57
• I believe this answer and the comment that follows it are the complete state of the art. – Jeffε Jan 22 '12 at 18:35
• Well this was dissapointing – sture Jan 23 '12 at 5:56
• For the record, JɛﬀE's comment seems to refer to Shir's answer below. – András Salamon Jun 23 '13 at 14:17
• I was referring to Max's answer, not Shir's, and to Raphael's comment on Max's answer. – Jeffε Mar 15 '14 at 22:32

If the complexity measure you are considering is query complexity, i.e., the number of times the machine has to look at the input to solve a particular problem, then there are many problems for which we have optimal algorithms. The reason for this is that lower bounds for query complexity are easier to achieve than lower bounds for time or space complexity, thanks to some popular techniques including the adversary method.

The downside, however, is that this complexity measure is almost excusively used in quantum information processing as it provides an easy way of proving a gap between quantum and classical computational power. The most notorious quantum algorithm in this framework is Grover's algorithm. Given a binary string $x_1,\dots ,x_n$ for which there exists a single $i$ such that $x_i=n$, you are required to find $i$. Classically (without a quantum computer), the most trivial algorithm is optimal: you need to query this string $n/2$ times on average in order to find $i$. Grover provided a quantum algorithm that does so in $O(\sqrt n)$ queries to the string. This has also been proven optimal.

• Indeed, query complexity is the underlying basis for Max's answer. For most problems, any algorithm provably "has to read the entire input" or at least a constant fraction of the input. – Jeffε Jan 24 '12 at 10:14
• If you are willing to change your model, quite a few lower bounds in data structures are tight. See Lower Bounds for Data Structures for pointers to good references for lower bounds in data structures.
• From the $\Omega(n log n)$ bound for sorting in the comparison model that some people have mentioned here, you can obtain a similar bound for the convex hull problem by considering the case where the input is composed of points along the graph of a increasing function in the first quadrant of the plane.
• +1 for mentioning data structures. But I don't think it's possible to obtain a useful lower bound for convex hulls via the comparison lower bounds for sorting. The reason is that the comparison model isn't powerful enough to compute convex hulls at all. What works instead is to use a more powerful model such as algebraic decision trees in which hulls can be computed, and then to adapt the lower bound for sorting to this more powerful model. – David Eppstein Jan 24 '12 at 21:20
• Makes sense, thanks for the clarification! – Abel Molina Jan 27 '12 at 9:20
1. Comparison sorting using $O (n \log n)$ comparisons (merge sort, to name one) is optimal, the proof involves simply calculating the height of a tree with $n!$ leaves.

2. Assuming the Unique Games Conjecture, Khot, Kindler, Mossel and O'donnell showed that it is NP-complete to approximate Max-Cut better than Goemans and Williamson's algorithm. So in that sense G&W is optimal (assuming also that $P\neq NP$).

3. Some distributed algorithms can be shown to be optimal with respect to some conditions (e.g., the proportion of adversarial processors), but since you mentioned Turing machines, I guess that's not the type of examples you're looking for.

• Whether item 2 answers the question or not depends on what the asker means by “optimal,” although I doubt that the asker is asking in that sense (otherwise there are many, many tight approximability results which do not even require UGC). Moreover, I do not think that either item 1 or 3 answers the question. – Tsuyoshi Ito Jan 21 '12 at 16:31
• @TsuyoshiIto, it's hard to guess what exactly the asker meant, which is what made me try answers in various directions in hope of hitting something useful for him/her. What makes you say that (1) is not a valid answer, by the way? – Shir Jan 21 '12 at 16:34
• The asker specifically asks an algorithm optimal for Turing machine. – Tsuyoshi Ito Jan 21 '12 at 20:21
• Is "comparison sorting" actually a "problem"? Or is it a problem and a restriction on the model of computation? – Jeffε Jan 22 '12 at 18:36

Suppose you are given input $w = \langle M, x, t \rangle$ and are asked to decide if RAM machine $M$ terminates on input $x$ after $t$ steps. By the time hierarchy theorem, the optimal algorithm to decide this is to simulate the execution of $M(x)$ for $t$ steps, which can be done in time $O(t)$.

(Note: for Turing machines, simulating the execution of $M$ takes $O(t \log t)$ steps; we only know a lower bound of $\Omega(t)$. So, this is not quite optimal for Turing machines specifically).

There are some other problems which contain the version of the halting problem as a sub-case. For example, deciding whether a sentence $\theta$ is a consequence of the WS1S takes time $2 \uparrow \uparrow O(|\theta|)$ and this is optimal.

I am unsure what you mean by "non-trivial", but how about this. $L = \{0^{2^k} | k \geq 0\}$. This language is not regular therefore, any TM deciding it must run in $\Omega(n \log n)$. The simple algorithm (crossing every other 0) is optimal.

If you allow dynamic data structure problems, we know some super-linear time optimal algorithms. This is in the cell probe model, which is as strong as the word RAM, i.e. this is not a restricted model such as algebraic decision trees.

One example is keeping prefix sums under dynamic updates. We start with an array of numbers $A, \ldots, A[n]$, and the goal is to keep a data structure that allows the following operations:

• Add $\Delta$ to $A[i]$, given $i$ and $\Delta$
• Compute the prefix sum $\sum_{j = 1}^i{A[i]}$, given $i$

You can easily support both operations in $O(\log n)$ time with a data structure based on an augmented binary tree with $A[i]$ at the leaves. Patrascu and Demaine showed this is optimal: for any data structure there is a sequence of $n$ additions and prefix sum queries that must take $\Omega(n\log n)$ time total.

Another example is union find: start with a partition of $\{1, \ldots n\}$ into singletons, and keep a data structure that allows the two operations:

• Union: given $i$ and $j$, replace the part containing $i$ and the part containing $j$ with their union
• Find: given $i$, output a canonical element from the part containing $i$

Tarjan showed that the classical disjoint set forest data structure with the union by rank and path compression heuristics takes $O(\alpha(n))$ time per operation, where $\alpha$ is the inverse Ackermann function. Fredman and Saks showed this is optimal: for any data structure there exists a sequence of $n$ union and find operations which must take $\Omega(n\alpha(n))$ time.

Many streaming algorithms have upper bounds matching their lower bounds.

there are two somewhat similar search algorithms that [my understanding is] are optimal based on a particular constraints on the input ordering/distribution. however presentations of the algorithms do not typically emphasize this optimality.

• golden section search for finding the maximum or minimum (extremum) of a unimodal function. assumes input is a unimodal function. finds it in logarithmic time on average. as I recall there may have been a proof of optimality in the book Structure & Interpretation of computer programs by abelson & sussman.

• binary search finds a point in logarithmic time on average in a sorted list, but requires input to be sorted.

am citing wikipedia above but it does not have the proofs that they are optimal, maybe some other references that prove optimality can be found by the audience.

Many sublinear time algorithms have upper bounds matching their lower bounds.

• Flagged as a duplicate. – Jeffε Jan 24 '12 at 10:09
• Sublinear time algorithm and streaming algorithm are different areas. – Bin Fu Jan 24 '12 at 15:09
• That's true, but you should combine the answers into one. – Suresh Venkat Jan 24 '12 at 22:37
• Some examples of optimal sublinear time algorithms can be – Bin Fu Jan 25 '12 at 16:05
• it is also not clear why this is not a duplicate of the query complexity answer. – Artem Kaznatcheev Jan 26 '12 at 16:39