# Is there a decision algorithm with time complexity of Ө(n²)?

Is there a decision problem with a time complexity of Ө(n²)?

In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N².

I thought about searching for the biggest number in matrix but the problem is that matrix is an input of O(n²) so the solution is linear.

It doesn't need to be known problem, a hypothetical one would suffice as well.

EDIT I looking for a regular programing problem - not a Turing Machine.

It's could be an arrays, strings, graph etc.

• You may want to specify a computation model, e.g. Turing Machines, Random Access Machines, ... What is quadratic in one model is not necessarily so on others.
– chi
Sep 26 '16 at 8:01
• "Regular programming problem" is not a model of computation. But it sounds like a random access machine. Sep 26 '16 at 8:54
• What are you willing to assume? For example, there are such lower bounds assuming the Strong Exponential Time Hypothesis (SETH), but not everyone believes it is true.
– Juho
Sep 26 '16 at 11:07
• @Abdul Yes. In most "practical" cases, you are assuming a RAM model. In Turing Machines, for instance, complexity may differ. E.g. consider the task: given $(i,x_1,\ldots,x_n)$ return $x_i$. In RAM this can be solved in $O(1)$ since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$. All "reasonable" computational models have complexity which differ by a polynomial factor, at most, so e.g. solving "P vs NP" in a model suffices for all other models.
– chi
Sep 26 '16 at 12:37
• @Abdul Further, to make things worse, some subfields have different conventions. When dealing with matrices, we usually write $O(n^2)$ even if it is actually linear on the size of the matrix, since we prefer to call $n$ the length of the side. The trivial factorization algorithm for a natural $n$ is $O(n)$ but we regard it as exponential on the number of the digits of $n$, and don't call it "linear-time". One needs to adapt to these conventions and understand their actual meaning -- at the beginning it can be quite confusing.
– chi
Sep 26 '16 at 12:42

Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.
For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.