Determining most efficient algorithm for a problem
Note that there is a problem with no maximally efficient algorithm.

The problem "Is it the case that x has an even number of 1s and

the Turing machine M halts within length(x) steps?" is such that

$\:$ if M halts then the problem takes linear time to solve, since for inputs whose length exceeds

$\:$ the amount of time it takes for M to halt, the algorithm will have to look at each bit of x
 $\;\;\;\;$ and
$\:$ if M does not halt then the problem can be solved

$\:$ in constant time, since the answer is no for all x

.
Therefore, deciding how efficient the most efficient algorithm for some problem is, to the

extent that makes sense, is at least as hard as the halting problem. $\:$ On the other hand,

you may be interested in the circuit minimization problem and/or DFA minimization.