0
$\begingroup$

Are there problems, for which best algorithms have worst run time O(input_length^2) and it is proven, that this worst time cannot be substantially improved (better algorithms do not exist).

EDIT: This question is different from Are there any known lower-bounds for complexity on Non-determinsitic machines , because I have in mind deterministic machine. For example, simple one-processor computer. Question Problems that provably require quadratic time is more like this.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ See also cs.stackexchange.com/q/38357/755, cs.stackexchange.com/q/30320/755, cs.stackexchange.com/q/6732/755, and lower-bounds. $\endgroup$ – D.W.♦ Jun 20 '16 at 18:42
  • 1
    $\begingroup$ @D.W. Definitely not a dupe of the question about nondeterministic machines! $\endgroup$ – David Richerby Jun 20 '16 at 20:55
  • 1
    $\begingroup$ @DavidRicherby, it's not the same question, but the answer to that question answers this one as well (that answer covers deterministic machines as well). DSblizzard, take another look at the answer to that question -- I think you'll find it contains all the information needed to answer this question too. $\endgroup$ – D.W.♦ Jun 20 '16 at 21:10