Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm \mathbb A deciding TAUT has a polynomial time computable sequence witnessing that \mathbb A is not almost optimal. The result extends to every \Pi_t^p-complete problem with t\ge 1; however, we show that assuming the Measure Hypothesis there is a problem which has no almost optimal algorithm but has an algorithm without hard sequences.