I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$.

The problem needs to have the following properties:

  1. $\Omega(n^2)$ runtime proof for any algorithm - first priority is to have as simple as possible lower bound argument.
  2. $O(n^2)$ algorithm, if possible, simple one as well.
  3. Output size of $O(n)$ (or smaller). Obviously any problem which requires $\Omega(n^2)$ lengthed output required at least similar run time, but that's not what I'm looking for. Notice that any decision problem fits here.
  4. (if possible) a "natural" problem. Without a formal definition, a problem any CS graduate would recognize is preferable.

I was recently asked about such problem but couldn't come up with a simple one. The first problem that came to mind was $3SUM$, which was conjuctured to be a $\Omega(n^2)$ runtime problem. This was not simple enough and furthermore, the conjucture was recently proven false :o.

Going to an extremely unnatural problem, I believe that the problem that gets as an input a deterministic TM and input $\langle M \rangle,x$, and outputs the position of the tape head after $(|M|+|x|)^2$ steps when it's running on $x$ probably answers the question.

If you absolutely need to, lets agree that we're using the single-tape TM model, although I prefer problems whose runtime is independent on the exact model (as long as it's a reasonable one).

So, can we find a simple (to prove), natural (well known) problem whose runtime is $\Theta(n^2)$?

  • $\begingroup$ I think "Given natural numbers $x$, $y$, compute $x+y$" qualifies. Also, note this question. $\endgroup$
    – Raphael
    Commented Sep 26, 2014 at 13:07
  • 2
    $\begingroup$ The only way we know how to prove superlinear lower bounds on multitape Turing machines is through diagonalization. For single-tape Turing machines, you can get a bit better using crossing sequences, but not as far as $n^2$ unless perhaps you restrict the space. $\endgroup$ Commented Sep 26, 2014 at 13:34
  • 2
    $\begingroup$ See here for another related question; input reversal seems to be a good candidate. $\endgroup$
    – Raphael
    Commented Sep 26, 2014 at 13:36
  • $\begingroup$ I don't think you can do it with a decision problem, because the best found lower bound for NP is O(n). $\endgroup$ Commented Mar 4, 2015 at 14:38
  • 1
    $\begingroup$ @Daniel - no. I'm interested in decision problems that we can prove having no subquadratic algorithm. The fact that we have some problems with quadratic algorithms is obvious :). $\endgroup$
    – R B
    Commented Dec 14, 2016 at 14:57

2 Answers 2


Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine.

By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound - probably one of the largest gaps in computer science.


As in the link provided by Raphael, Peter shows that Input Reversal requires $\Theta(n^2)$ time on vanilla single-tape TMs. For a decision problem, the language $$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$$ also provably needs $\Theta(n^2)$ time to compute. To see this, use Peter's communication complexity argument , along with a classical result that $EQ_n$ needs $\Theta(n)$ bits of communication, to show the quadratic lower bound of $L$. The similar approach works for a more natural one $L = \{xx \mid x \in \{0,1\}^\ast \}$.

By the way, it is worth mentioning that the "crossing sequence method" mentioned by Yuval is (to my best knowledge) mathematically equivalent (or, maybe, inforior) to the communication complexity one.

For another candidate that does not directly answer your question, Ryan Williams proved that $\mathsf{SAT}$ cannot be decided in $O(n^{2 \cos(\pi/7)})$ time and simultaneously $n^{o(1)}$ space on RAMs. While the constant $2 \cos(\pi/7) \approx 1.8$ seems quite magical, the initial idea that comes from Fortnow, is ingenious but not so involved. Refer to page 101 in the textbook of Barak and Arora for an exposition of the idea.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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