<p>See this lower bound for sorting, for example:
<a href="http://planetmath.org/lowerboundforsorting" rel="nofollow noreferrer">http://planetmath.org/lowerboundforsorting</a></p>

<p>You typically need to assume something about the algorithm's access to the input data. In this case, the assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the pairwise comparisons effectively induce a binary tree on $n!$ leaves -- one leaf for each possible input ordering. Such a tree must have depth $\Theta(\log(n!))=\Theta(n\log n)$.</p>

<p>Note that in a different data access model, algorithms can achieve linear-time sorting:
<a href="https://en.wikipedia.org/wiki/Radix_sort" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Radix_sort</a></p>

<p>Obiously, faster than linear time is impossible, since you have to at least read all of the inputs.</p>

CC BY-SA 3.0
2017-03-12T17:11:10.477Z
This is not entirely correct for the example. You do not _need_ to sort the elements in order to find the _single_ duplicate. You can do it in linear time easily, but you need at least two pointers, each of size of log n bits.
PsySp
CC BY-SA 3.0
2017-03-12T17:25:17.560Z
Ah, ok -- was answering a different part of the question, before the "For example". I think the answer does offer some insight for that part, but it's a judgement call.
Aryeh
CC BY-SA 3.0
2017-03-12T12:12:02.603Z
2017-03-13T01:45:50.510Z
2017-03-13T01:45:50.510Z
Aryeh
<p>What you are asking for is methods in proving lower bounds on the computational complexity (measured in space, time, etc) of given computational problems, and the answer is mostly that we have made very little progress on general methods for this and that is essentially the entire subject of complexity theory.</p>

<p>That being said, if you're more interested in estimates that are almost certainly going to be useful, you can use the tool of the <a href="https://en.wikipedia.org/wiki/Polynomial-time_reduction" rel="nofollow noreferrer">reduction</a> which will essentially place your problem in a partial order representing the difficulty of problems, allowing you to then think about how hard it is <strong>relative</strong> to the other problems we study, given some granularity of reduction (in the link, reductions in FP).</p>

CC BY-SA 3.0
2017-03-12T20:43:49.100Z
2017-03-12T20:43:49.100Z
Samuel Schlesinger
<p>Are there standard techniques to show that no algorithms exist for given complexity constraints?</p>

<p>For example, consider the following problem. The input is a list of items with exactly one duplicate, and you wish to find the duplicate item.</p>

<p>How do you formally prove that there cannot be an algorithm that does this in constant space and linear time?</p>

CC BY-SA 3.0
2017-03-12T04:26:51.153Z
[Adversary argument](http://jeffe.cs.illinois.edu/teaching/algorithms/notes/29-adversary.pdf)?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2017-03-13T05:40:12.213Z
I don't see how to solve this problem in constant space with any amount of time, since you need superconstant space just to write down the answer.... But anyway one answer to your question is *information theory*, also *communication complexity* which is closely related.
usul
<proofs><complexity>
Formally proving no algorithm exists
user890123818239
# Formally proving no algorithm exists

(Asked by: username_0 on 2017-03-12)

Are there standard techniques to show that no algorithms exist for given complexity constraints?

For example, consider the following problem. The input is a list of items with exactly one duplicate, and you wish to find the duplicate item.

How do you formally prove that there cannot be an algorithm that does this in constant space and linear time?

**Tags:** proofs, complexity

> **Comments:**
> **username_1**: [Adversary argument](http://jeffe.cs.illinois.edu/teaching/algorithms/notes/29-adversary.pdf)?  
> **username_2**: I don't see how to solve this problem in constant space with any amount of time, since you need superconstant space just to write down the answer.... But anyway one answer to your question is *information theory*, also *communication complexity* which is closely related.  

---

## 2 answers

### Answer by username_3 on 2017-03-12. Score: 3 | Accepted answer

See this lower bound for sorting, for example:
<http://planetmath.org/lowerboundforsorting>

You typically need to assume something about the algorithm's access to the input data. In this case, the assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the pairwise comparisons effectively induce a binary tree on $n!$ leaves -- one leaf for each possible input ordering. Such a tree must have depth $\Theta(\log(n!))=\Theta(n\log n)$.

Note that in a different data access model, algorithms can achieve linear-time sorting:
<https://en.wikipedia.org/wiki/Radix_sort>

Obiously, faster than linear time is impossible, since you have to at least read all of the inputs.

> **Comments:**
> **username_4**: This is not entirely correct for the example. You do not _need_ to sort the elements in order to find the _single_ duplicate. You can do it in linear time easily, but you need at least two pointers, each of size of log n bits.  
> **username_3**: Ah, ok -- was answering a different part of the question, before the "For example". I think the answer does offer some insight for that part, but it's a judgement call.  

---

### Answer by username_5 on 2017-03-12. Score: 3

What you are asking for is methods in proving lower bounds on the computational complexity (measured in space, time, etc) of given computational problems, and the answer is mostly that we have made very little progress on general methods for this and that is essentially the entire subject of complexity theory.

That being said, if you're more interested in estimates that are almost certainly going to be useful, you can use the tool of the [reduction](https://en.wikipedia.org/wiki/Polynomial-time_reduction) which will essentially place your problem in a partial order representing the difficulty of problems, allowing you to then think about how hard it is **relative** to the other problems we study, given some granularity of reduction (in the link, reductions in FP).


---

