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.
What are some quadratic run time tasks (algorithms)?
algorithms;asymptotics;lower bounds