3 ms·

there is an O(n) Turing machine that guesses only the correct binary number. you just don't know which.