Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
4  
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
4  
"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
show 3 more comments

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)

share|improve this answer
3  
"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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.