An Exercise from a Textbook:

L3 := {ε,01,0011}

is L3 ∈ DTime(log(n))

The answer says yes it is, it is even in DTime(1).

How is this possible? I would say it takes at least n steps to check the word. How is it possible to do it in less than n steps?


2 Answers 2


To add to old's answer, saying a TM runs in $O(1)$ means that the number of steps the TM makes cannot become infinitely large depending on the size of the input, and is always bounded by some constant. It is true that in this case, for some inputs, the number of steps will be exactly the size of the input, and technically depend on the size of the input. However, this isn't the case for any input of size $>4$, and therefore the $O(1)$ notation is correct.


Your Turing machine just needs to read the first four symbols one the input tape that will be sufficient to to solve the problem $L3$.

  • $\begingroup$ yes thats what I thought too and this means n-symbols not log(n) symbols? $\endgroup$ Jun 25, 2018 at 9:14
  • 1
    $\begingroup$ This means $O(1)$ symbols $\endgroup$
    – old
    Jun 25, 2018 at 9:16
  • $\begingroup$ ok, O(1) means constant, but if the input is the empty Word or 01, than it wouldnt have to read 4 symbols? So it would be a bit faster? $\endgroup$ Jun 25, 2018 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.