Determining whether the output of an algorithm is constant
It's not decidable. Given any program $P$, you can write a program $Q$ running in time (say) $O(n^2)$, which on input $n$ simulates $n$ steps of $P$, and returns 1 if $P$ halted. Then $P$ doesn't halt if and only if $Q$ always outputs 0.

This shows that your problem is $\Pi_1$-hard (since the halting problem is $\Sigma_1$-hard). It is also clearly in $\Pi_1$, and so it is $\Pi_1$-complete. (For the definition of $\Pi_1$, check out the arithmetical hierarchy on Wikipedia.)