Is there a decision algorithm with time complexity of Ө(n²)?
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 &gt; 0$ unless the strong exponential time hypothesis is false.