<p>I recently had an interview, at which I was asked to solve the following problem: you have a sorted array of integers, and you need to find if there are 3 numbers that sum to 0. The brute force solution gives $O(n^3)$ complexity. Given that it is sorted, we can iterate over 2 numbers, and the third one using binary search. It gives $O(n^2\log(n))$ complexity. In fact, there exist a solution with $O(n^2)$ complexity, but apparently this is the best what we can get.</p>

<p>I was thinking is there a way to show in advance that $O(n^2$) is the best, and I came up with the following considerations. They are based on the postulate that <strong>if the solution of a problem contains $I$ amount of information, then the minimum amount of operations required to get it is $O(2^I)$.</strong> Indeed, if we have $n$ equally probable independent answers, i.e., $I=log(n)$, the only way to solve the problem is to try each of them, i.e. spend $O(n)$ operations. Here are the considerations applied to the problem above.</p>

<p>1) Let us imagine that the array is unsorted. In this case any combination of 3 digits can be a solution, and therefore the amount of information in the answer is $3\log(n)$.</p>

<p>2) Let us assume that the best sorting algorithm has a complexity $O(n\log(n))$, so we can consider that $\log(n\log(n))$ is the amount of information it gives us about the array. Or in other words, the entropy of the array was decreased on this amount.</p>

<p>3) Subtracting one from another, we get $3\log(n) - \log(n\log(n)) = 2\log(n) - \log(\log(n))$. This is the amount of information in the solution of the problem. </p>

<p>4) According to the postulate, the algorithm complexity must be at least $O(2^{2\log(n) - \log(\log(n))}) = O(n^2/\log(n))$. <strong>This coincides with the fact that there exist a solution with the complexity $O(n^2)$, but not $O(n\log(n))$.</strong></p>

<p>What do you think? Could you advice me to read something similar?</p>

CC BY-SA 3.0
2015-12-24T04:38:40.443Z
There are two main methods for proving lower bounds in restricted models of computation like decision trees: 1. information theoretic, 2. adversary argument. You can start by checking Faith Ellen's video lecture for her data structures course: [1](https://www.youtube.com/watch?v=Mz7g-MQBkfM), [2](http://www.youtube.com/watch?v=Z_EtkOaVXao), [3](http://www.youtube.com/watch?v=ILa6W3sCQJ4), [4](http://www.youtube.com/watch?v=6ZvfpB7nqUI).
Kaveh
CC BY-SA 3.0
2015-12-24T05:27:10.470Z
What is the input domain? All integers? Only positive integers?
orlp
CC BY-SA 3.0
2015-12-24T06:02:57.190Z
In this particular task negative integers are of course allowed. Otherwise the problem would not have a solution.
Sergey Demyanov
CC BY-SA 3.0
2015-12-24T09:04:19.847Z
Your postulate (which is a far stronger claim than for instance $P\not = NP$) is false. Sorting has $n!$ possible answers, but it definitely doesn't require $\Omega(n!)$ time.
Tom van der Zanden
CC BY-SA 3.0
2015-12-24T10:55:28.087Z
Tom, n! possible answers means log(n!) information only when the answers are independent. In the case of sorting, it is easy to show that it is not true: if a pair of elements in a permutation is in the wrong order, it makes all other permutations with the same pair invalid as well.
Sergey Demyanov
CC BY-SA 3.0
2016-01-01T05:34:09.280Z
Does your postulate hold for the problem of solving a system of linear equations?
Igor Shinkar
<complexity>
Is there any theory that allows to compute the computational complexity boundaries like this?
Sergey Demyanov
# Is there any theory that allows to compute the computational complexity boundaries like this?

(Asked by: username_0 on 2015-12-24)

I recently had an interview, at which I was asked to solve the following problem: you have a sorted array of integers, and you need to find if there are 3 numbers that sum to 0. The brute force solution gives $O(n^3)$ complexity. Given that it is sorted, we can iterate over 2 numbers, and the third one using binary search. It gives $O(n^2\log(n))$ complexity. In fact, there exist a solution with $O(n^2)$ complexity, but apparently this is the best what we can get.

I was thinking is there a way to show in advance that $O(n^2$) is the best, and I came up with the following considerations. They are based on the postulate that **if the solution of a problem contains $I$ amount of information, then the minimum amount of operations required to get it is $O(2^I)$.** Indeed, if we have $n$ equally probable independent answers, i.e., $I=log(n)$, the only way to solve the problem is to try each of them, i.e. spend $O(n)$ operations. Here are the considerations applied to the problem above.

1) Let us imagine that the array is unsorted. In this case any combination of 3 digits can be a solution, and therefore the amount of information in the answer is $3\log(n)$.

2) Let us assume that the best sorting algorithm has a complexity $O(n\log(n))$, so we can consider that $\log(n\log(n))$ is the amount of information it gives us about the array. Or in other words, the entropy of the array was decreased on this amount.

3) Subtracting one from another, we get $3\log(n) - \log(n\log(n)) = 2\log(n) - \log(\log(n))$. This is the amount of information in the solution of the problem.

4) According to the postulate, the algorithm complexity must be at least $O(2^{2\log(n) - \log(\log(n))}) = O(n^2/\log(n))$. **This coincides with the fact that there exist a solution with the complexity $O(n^2)$, but not $O(n\log(n))$.**

What do you think? Could you advice me to read something similar?

**Tags:** complexity

> **Comments:**
> **username_1**: There are two main methods for proving lower bounds in restricted models of computation like decision trees: 1. information theoretic, 2. adversary argument. You can start by checking Faith Ellen's video lecture for her data structures course: [1](https://www.youtube.com/watch?v=Mz7g-MQBkfM), [2](http://www.youtube.com/watch?v=Z_EtkOaVXao), [3](http://www.youtube.com/watch?v=ILa6W3sCQJ4), [4](http://www.youtube.com/watch?v=6ZvfpB7nqUI).  
> **username_2**: What is the input domain? All integers? Only positive integers?  
> **username_0**: In this particular task negative integers are of course allowed. Otherwise the problem would not have a solution.  
> **username_3**: Your postulate (which is a far stronger claim than for instance $P\not = NP$) is false. Sorting has $n!$ possible answers, but it definitely doesn't require $\Omega(n!)$ time.  
> **username_0**: Tom, n! possible answers means log(n!) information only when the answers are independent. In the case of sorting, it is easy to show that it is not true: if a pair of elements in a permutation is in the wrong order, it makes all other permutations with the same pair invalid as well.  
> **username_4**: Does your postulate hold for the problem of solving a system of linear equations?  

---

## 0 answers

