Take the 2-minute tour ×

I know of the Bubble-sort, Insertion-sort etc. but there are more efficient algorithms for sorting. By the Time Hierarchy Theorem, there are problems that can be solved in O(n^2) but not in O(n^r) for any real r < 2. The constructions used for it's proof are not very natural. What is a good example of a problem whose most efficient solution requires quadratic time?

I am looking for something that has preferably the following qualities:

  • It is simple and easy to understand
  • Something that is used frequently
  • It can be proved that O(n^2) is the best run-time for a correct solution

Small caveat - The output should not be large. (If you want the sum of every pair of integers from a given list, it obviously requires quadratic time to output them). You can assume that it should be a decision problem, i.e. one with an yes-no answer. Also let us assume the time complexity O(n^2) is a function of input size, i.e. n is the number of bits required to represent the input.

share|improve this question
3SUM comes to mind, but it's still open whether we can beat O(n²) (and I wouldn't say that it's used frequently). –  Nabb Dec 16 '12 at 13:39

3 Answers 3

Matrix multiplication has a theoretical lower bound of Ω(n2), since all n2 entries need to be processed. The best known algorithm to date (according to the above-linked Wikipedia article) has complexity O(n2.3727). The naive algorithm has complexity n3.

According to the Wikipedia article on Computational complexity of mathematical operations, back-substitution of a triangular matrix to obtain n solutions is O(n2). There are probably many other examples around on the web.

share|improve this answer
That is not correct. In formal complexity theory, Run-time is a function of input size. It takes n^2 size to represent an nxn matrix. So the lower bound is in fact linear. –  akashnil Dec 16 '12 at 7:10
@akashnil - Yeah, I thought about that. However, I'm just going with the standard terminology used in the literature. –  Ted Hopp Dec 16 '12 at 7:12
@akashnil - I take it back. Consider the outer product of two 1xn matrices. The input size is 2n (= O(n)). The output size is O(n^2). Theoretical complexity is O(n^2). Also, see my updated answer for another example. –  Ted Hopp Dec 16 '12 at 7:14
You are right. I edited the question to make it more interesting. There are trivial problems that require O(n^2) time without the output size limitation - i.e. if you want the sum of every pair of integers from a given list. –  akashnil Dec 16 '12 at 7:19
@akashnil - That's a more challenging problem. Not that I have something in mind at the moment, but would you be satisfied with an O(n^2) problem that has O(n) output size instead of O(1)? –  Ted Hopp Dec 16 '12 at 7:50

This is almost a year later, but I think I have an answer: partial order discovery.

Think about sorting on a total ordering for a moment. You have a sequence of n objects (we will assume they are distinct), and a comparison operation which tests two elements to see if one is less than or equal to the other.

You are trying to discover which permutation the elements are in. There are n! possible permutations, so you're trying to discover a number between 1 and n!. Each comparison gives you one bit of information. To discover a number between 1 and n! requires discovering log(n!) bits. Therefore the number of comparisons required is also log(n!) bits, or:

log(n!) = n log n + o(n log n) = Ω(n log n) bits

(All logarithms are, of course, in base 2.)

You cannot do better than this. If each query gives you one bit of information, and you need to discover at least Ω(n log n) bits, then you need Ω(n log n) comparisons. If you think you can do better, take it up with Shannon, Chaitin and Kolmogorov.

But what's even better is that algorithms are known which can do it even in the worst case (e.g. heap sort). In that sense, heap sort is asymptotically optimal.

(Note that you can do better if you have a query operation which returns more than one bit of information. If you can come up with one that returns Ω(log n) bits, for example, then you should be able to sort in Ω(n) time. See radix sort for more details.)

This analysis works with all sorts of algorithms. Finding a single thing in a sequence of n things requires discovering a number between 1 and n, which means discovering log n + O(1) bits. If your query operation returns one bits, then it takes Ω(log n) queries to do the search. (See binary search for details.)

I think you can see where I'm going with this.

Now suppose you have n elements which have a partial order relation on them, but you don't know what it is and want to find out. What you do have, though, is a query which compares two elements x and y, and returns "true" if x is less than or equal to y in the partial order.

There is an obvious algorithm to discover the partial order which takes Ω(n^2) time: simply compare each element against each other element.

But is this optimal? Well, the query operation returns one bit of information. The number of partial orders on n elements is given by Sloane's A001035. If I'm reading it right, this sequence is Ω(2^(n^2)), which means that to discover a partial order, you need:

Ω(log 2^(n^2)) = Ω(n^2) bits

That is, you can't do better than Ω(n^2) time, so this is an asymptotically optimal algorithm.

"So", I hear you ask, "I buy the fact that the size of the input is n. But isn't the size of the output O(n^2), so it's actually a linear algorithm in some deep technical sense?"

Well... maybe. I don't really have time to go into the details right now, but I'll answer it with a question.

In the case of plain old sorting, we might be given n distinct elements. To be distinct, they need to be labelled with n distinct labels. Storing n distinct labels means storing n numbers, each of which is between 1 and n. Each of those numbers requires log n bits to represent it, so the total size of the problem is n log n bits. So why don't we say that heap sort is linear in the size of the problem?

share|improve this answer
What you said in the last paragraph about heap sort is absolutely correct. When talking about complexity so precisely (n versus n log n) we need to be very careful. Maybe if we ignore the log factors, this won't be an issue anymore. Suppose the input is a string of n bits (with some encoding that doesn't matter). The required output is also of size n bits or fewer. The run time is some function f(n) which is O(n^{2+eps}) and omega(n^{2-eps}) for all eps > 0. Maybe that would be a well defined question, although a bit complicated. –  akashnil Jan 16 '14 at 15:10

You are making a fundamental mistake of mixing computational models.

The time heirarchy theorem is about Turing machines while most of the other bounds have either their own models (like comparison model for sorting) or are usually about the RAM model.

So the real question is, which computational model are you talking about?

Also, talking about a best algorithm being no worse than O(n^2) (BigOh) is nonsense. BigOH is an upper bound. You probably meant to use Theta.

share|improve this answer
I'm not sure why this was downvoted. –  templatetypedef Jan 17 '14 at 4:11

Your Answer


