Time complexity and optimality

Question

If a problem has worst-case lower bound Ω(n^2) and there is an algorithm with W(n) ∈ O(n), What can we say about the possibility, importance and order of optimality about this problem and algorithm?

Answer 1

I'll consider decision problems only, for optimisation problems the question could be quantified in plenty of ways.

I assume that you are asking the following: if a language $L \not\in \mathrm{DTime}(n^2)$ and another language $L' \in \mathrm{DTime}(n)$, how close in some sense $L'$ could be to $L$?

One of the more or less natural measures of closeness is the following one. For each $n \in \mathbb{N}$, $\mathbf{P}(L(x) = L'(x)) > 0$ where $x$ is uniformly distributed among $\{0,1\}^n$. Surprisingly, there exists a language $L \in \mathrm{DTime}(n^2)$ such that for any $L' \in \mathrm{DTime}(n)$ there exists infinitely many values of $n$ such that $\mathbf{P}(L(x) = L'(x)) = 0$. One can prove that using diagonalisation in a very similar way to time hierarchy Theorem:

An algorithm $B$ for the language $L$ will act as follows. $B(x)$ will run the algorithm corresponding to the string $|x|$ in binary form for $|x|^{1.5}$ steps (this takes $O(|x|^{1.5} \log |x|)$ time) and answers $0$ if $\langle|x|\rangle$ (the algorithm) did not halted and $1-\langle|x|\rangle(x)$ otherwise. For each algorithm in $\mathrm{DTime}(n)$ there are infinitely many equivalent algorithms and therefore the length of the encoding string of one of them is such that $|x|^{1.5} > cn$ where $c$ is a constant such that $\langle|x|\rangle$ does at most $cn$ steps. Thus $B$ will run $\langle|x|\rangle$ for sufficient number of steps and return the opposite value for any $y \in \{0,1\}^{|x|}$.