Examples of simple/common problems with quadratic running time

Question

Are there some examples of simple or common problems which have (in a practical sense) quadratic complexity? I would have thought there were a lot of them, but upon further investigation, I can't seem to find any. (see https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations)

• Bubble sort / insertion sort are $O(n^2)$ worst-case, but there are tons of simple $O(n \log n)$ sort algorithms
• Multiplication of $n$-bit numbers is $O(n^2)$ for the conventional method, but then you have Karatsuba multiplication which is $O(n^{log_2 3} \approx n^{1.58})$
• Matrix multiplication is $O(n^3)$ for conventional implementation but in the $O(n^{2.376})$ to $O(n^{2.807})$ range for more clever implementations
• Fast Fourier Transform is $O(n \log n)$ instead of the simple $O(n^2)$ DFT
• Dijkstra's algorithm was $O(|V|^2)$ but someone thought of a $O(|E|+|V| \log |V|)$ implementation

Answer 1

It is true that many algorithms that have quadratic running time are not the state of the art for their problems today. Among which are quadratic sorting algorithms for example bubble-sort, select-sort and insertion-sort, which are overcome by merge-sort and heap-sort. On a side note, quick-sort, the standard sorting algorithm in different areas, has a worst running time of $O(n^2)$ and is only used because the probability of having bad running time (say worse than a constant factor of $O(n \log n)$ is very small and it has smaller overhead than the other efficient sorting algorithms).

Also solving maximum matching on bipartite graphs by reducing to maximum flow and solving with Ford and Fulkerson's method is $O(nm)$ which is quadratic in sparse graphs, which is again overcome by the algorithm from Hopcroft and Karp with running time $O(\sqrt n m)$.

However, some of the problems with quadratic running time are conjectured to be optimal up to a log factor. These problems are not only interesting because of their quadratic running time and that this time is probably optimal, but also because they lead a list of problems that are either as hard or strictly harder than them.

The 3-sum problem

• The problem. Given a set of $n$ integers, find if 3 of them add up to zero.
• Quadratic algorithm. Sort the values in the list. For each value $v$ in the list, look if there are two values summing up to $-v$. Such a search can be done in $O(n)$ in sorted array using sliding window technique. Since we do it for every element in the list we get a running time of $O(n \log n + n^2) = O(n^2)$. Note that the $n \log n$ is for sorting the array as a pre-processing step.
• Similar problems. The problem has many variants that are equivalent in a sense that have the same running time. Including the version of the problem where repetitions are not allowed or the version where you get three sets of values and you have to choose a value form list to sum up to zero (or to some value $v$). More Interesting are the reductions from the 3-sum problem variants to different Geometry problems as checking a point-set in the plane if three are co-linear. This problem is solvable in quadratic time using the point/line dual construction and is also expected to be optimal by the 3-sum conjecture. Another example is the Geombase problem, where you have a set of points each lying on one of the lines $y=0;y =1$ or $y=2$ and you need to find if there is a non horizontal line crossing three of the points. This problem is also equivalent to three sum in the sense that the reduction can be done in both directions. Similarly, the problem given a set of $n$ lines, do three of them intersect in one point is almost optimal in $O(n^2)$ if 3-sum conjecture is true.

---

The orthogonal vectors problem.

• The problem. Given a set of $n$ vectors of dimension $d$, are two of them orthogonal.
• The algorithm. For constant values of $d$, checking all pairs of vectors is in $O(d n^2) = O(n^2)$.
• Similar problems. Based on this conjecture, the following problems are almost optimal with a running time of $O(n^2)$. Edit distance, longest common subsequence and graph diameter in sparse graphs.

Here is a brief description for each of these problems:

• Edit distance: Given two strings, what is the least number of modifications (deletions, insertions..) are needed to make the strings equal. The problem can be generalized to a set of operations on both or one of the strings and cost for each operation and we want to minimize the total cost.
• Longest common subsequence: Given two strings, a subsequence of the string is a string resulting from the original string by deleting some characters. What is the longest string that is a subsequence of both input strings (Note that this problem is a special case of edit distance.
• Graph diameter is the longest shortest path in the graph, that means the minimum $d$ such that you can go from any node to any other node in less than $d$ steps.

Note there is a reduction from SAT to Orthogonal vectors proving that if the Orthogonal vectors conjecture fails, then SETH fails as well.