# Asymptotically optimal algorithms

Suppose one has an algorithm to solve a problem using at most f(n) computations with size of input n. How to prove, if such is the case, that this algorithm is the fastest possible for solving this problem?

I am aware of the open P!=NP problem, but I assume there are nontrivial problems where it has been proved that no faster algorithm exist? Which are such examples, and how is it proved?

-
Curiously, there is a large class of problems, including many known NP-complete ones where Levin's optimal search theorem provides a concrete algorithm, with guaranteed optimal asymptotic running time. The catch is that it is essentially impossible to analyze the running time of this algorithm without already knowing what the fastest possible running time is -- and also that Levin's algorithm has gigantic constant factors in its running time (where "gigantic" usually means "more than a googol"). – Henning Makholm Jan 22 '12 at 13:42

There's no general way, but only a wealth of techniques. Here are some examples:

• You prove that $f(n)$ is the minimum time required to read the input. For example, shortest path problem cannot be solved in less than $O(V + E)$.
• You prove that an algorithm with fewer will not get enough data about the input to output the correct solution. Thus, once can change the input in a way that changes the result without the algorithm "noticing" the difference. An example of this would be the proof that sorting cannot be done in less than $O(n \log n)$.
• You prove that an algorithm running in less time will lead to an existence of an algorithm that would solve a problem in less than the optimal time (e.g. sorting in less than $O(n \log n)$). This is achieved via reduction.
• You prove that the size of the output is in worst case as big as $f(n)$ therefore, one cannot take shorter time to compute it. For example, outputting the $n^{th}$ Fibonacci number cannot be solved in less than $O(2^{n})$ since the $n^{th}$ Fibonacci is ~ $\phi^{n}$ where $\phi$ is around $1.6$

There are more techniques, but those are some examples off the top of my head.

EDIT: As pointed out in the comments, the size of the $n^{th}$ Fibonacci numbers is exponential in the length (read log) of n, therefore it cannot be computed in less than $O(n)$ not $O(2^{n})$.

-
Your fourth example doesn't seem correct. The size of the output here is $\log_2 F_n$, not $F_n$. Binary exponentiation on the matrix $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$ should allow you to compute the $n^{th}$ Fibonacci number in time $O(n)$. – Qiaochu Yuan Jan 20 '12 at 23:02
For your fourth example, the $n$th Fibonacci number has $O(n)$ bits, so the $n$th Fibonacci number cannot be computed in $o(n)$. – Zach Langley Jan 21 '12 at 2:49
@QiaochuYuan How do you get $O(n)$? – Zach Langley Jan 21 '12 at 2:51
@Zach: hmm. I think I need to retract that. $F_n$ turns out to be the bottom right entry of $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]^n$, which can be computed using about $\log_2 n$ matrix multiplications using binary exponentiation (en.wikipedia.org/wiki/Exponentiation_by_squaring). The entries can be described using at most $n$ bits, so the total time needed is $O(M(n) \log n)$ where $M(n)$ is the complexity of whatever matrix multiplication algorithm you're using. I guess you can't do better than $O(n^2 \log n)$ this way. – Qiaochu Yuan Jan 21 '12 at 3:34
"less than $O(.)$" is not a very meaningful phrase. You should write "in o(.)$" instead. Also, note that the lower bound for sorting only applies to a certain setting and to comparisons. – Raphael Jan 21 '12 at 11:34 Sorting by comparisons can't be done in$o(n\log n)$because$k$comparisons can't distinguish among more than$2^k$orderings, and there are$n!$possible orderings, and Stirling's formula gives you$\log(n!)$is on the order of$n\log n$. (edited in response to spot-on comments by Raphael) - "faster than$O(.)$" is not very meaningful; you mean "in o(.)$. Note also that the famous bound only applies to comparison sorts. – Raphael Jan 21 '12 at 11:38