<p><a href="http://en.wikipedia.org/wiki/Matrix_multiplication" rel="nofollow noreferrer">Matrix multiplication</a> has a theoretical lower bound of Ω(<em>n</em><sup>2</sup>), since all <em>n</em><sup>2</sup> entries need to be processed. The best known algorithm to date (according to the above-linked Wikipedia article) has complexity O(<em>n</em><sup>2.3727</sup>). The naive algorithm has complexity <em>n</em><sup>3</sup>.</p>

<p>According to the Wikipedia article on <a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="nofollow noreferrer">Computational complexity of mathematical operations</a>, back-substitution of a triangular matrix to obtain <em>n</em> solutions is O(<em>n</em><sup>2</sup>). There are probably many other examples around on the web.</p>

<p>EDIT: A 2014 <a href="https://arxiv.org/pdf/1407.4972.pdf" rel="nofollow noreferrer">paper by Michele Borassi, <em>et al.</em></a>, discusses a number of decision problems (output size O(1)) that can be solved in O(<em>n</em><sup>2</sup>) time but not in O(<em>n</em><sup>2-<em>ε</em></sup>) for any <em>ε</em> > 0. (Of course, as always, these results depends on P ≠ NP, or, more precisely, that the <a href="https://en.wikipedia.org/wiki/Exponential_time_hypothesis" rel="nofollow noreferrer">Strong Exponential Time Hypothesis</a> is true.)</p>

<p>Their paper leads off with a modified <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow noreferrer"><em>k</em>-SAT problem</a>:</p>

<p><em>Input:</em></p>

<ul>
<li>two sets of variables <em>X</em> = {<em>x</em><sub><em>i</em></sub>}, <em>Y</em> = {<em>y</em><sub><em>j</em></sub>} of the same size;</li>
<li>a set <em>C</em> of clauses over these variables, such that each clause has at most size <em>k</em>; and</li>
<li>the two power sets &weierp;(<em>X</em>), &weierp;(<em>Y</em>) of <em>X</em> and <em>Y</em> (used to change the input size).</li>
</ul>

<p><em>Output:</em> <code>true</code> if there is an evaluation of all variables that satisfies all clauses, <code>False</code> otherwise.</p>

<p>Note that the unmodified <em>k</em>-SAT problem (where the input does not include the third bullet above) is NP-complete, so normally one thinks of it as an exponential-time problem. However, here the input size is itself exponential in the number of variables. They show that, with this modification, the problem can always be solved in quadratic time (simply try all possible evaluations). More to the point for this answer, they also show that this is the minimum time complexity for any algorithm that solves the problem.</p>

<p>One might object that this modified <em>k</em>-SAT problem is hardy natural. However, they then use this to show that a number of other problems, which do seem natural, also cannot be solved in less that O(<em>n</em><sup>2</sup>) time. The simplest one to state is the subset graph problem:</p>

<p><em>Input:</em> a set <em>X</em> and a collection <em>C</em> of subsets of <em>X</em>.</p>

<p><em>Output:</em> the graph <em>G</em> = (<em>C</em>, <em>E</em>), where, for each <em>C</em>, <em>C</em>′ ∈ <em>C</em>, (<em>C</em>, <em>C</em>′) ∈ <em>E</em> if and only if <em>C</em> ⊆ <em>C</em>′.</p>
Algorithmic task which requires quadratic time?
<p>I know of the Bubble-sort, Insertion-sort etc. but there are more efficient algorithms for sorting. By the <a href="http://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="noreferrer">Time Hierarchy Theorem</a>, there are problems that can be solved in O(n^2) but not in O(n^r) for any real r &lt; 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?</p>

<p>I am looking for something that has preferably the following qualities:</p>

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

<p>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 <a href="http://en.wikipedia.org/wiki/Decision_problem" rel="noreferrer">decision problem</a>, 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.</p>