Asymptotically optimal algorithms

Question

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?

Answer 1

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})$.

Answer 2

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)