🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Turing Machine Traces: all 10 questions

Quiz: Turing Machine Traces · Question 8 of 10

The palindrome TM takes about how many moves on an input of length n?

The palindrome TM takes about how many moves on an input of length n?

  1. A.About n
  2. B.About log n
  3. C.About n²/2
  4. D.About 2ⁿ
Answer & explanation

Correct answer: About n²/2

Each pair of matched symbols needs a walk across the remaining string; doubling n roughly quadruples the moves.

Can you get the rest right without peeking?

Take the timed Quiz: Turing Machine Traces quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →