patternMinor
Is there a decision algorithm with time complexity of Ө(n²)?
Viewed 0 times
withtimealgorithmdecisiontherecomplexity
Problem
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.
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.
Solution
Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.
In general the time hierachy theorem implies that there are such problems for most reasonable functions.
For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.
In general the time hierachy theorem implies that there are such problems for most reasonable functions.
For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.
Context
StackExchange Computer Science Q#63889, answer score: 6
Revisions (0)
No revisions yet.