Temporal complexity of a Turing machine for repeated lines

Question

I am trying to find out the time complexity of a turing machine that accepts repeated lines (ww) in three cases: a 1-tape deterministic machine, a 2-tape deterministic machine, and a 1-tape non-deterministic machine.

Now my thoughts are such that

• A 1-tape deterministic machine accepts O (n ^ 2) to find the midpoint (by repeatedly deleting the first and last characters at the input) and O (n ^ 2) to compare the first and second (since it must go back and forth n / 2 times, each time passing through n / 2 lines),

• 2-tape TM will take O (n ^ 2) to find the middle, O (n) to copy the second half to the second tape, then O (n) to compare the two halves at the same time,

• and the non-deterministic guesses about the midpoint and takes O (n ^ 2) to compare the two halves.

However, I feel that the three cases should not have the same O (n ^ 2) time complexity, so I wondered if my reasoning is incorrect somewhere (or am I correct and just think about the problem) Any input will be appreciated!

Answer 1

When using magnetic tapes, this logic seems correct. On a magnetic disk or solid-state drive, different algorithms, more suitable for accessing data non-linearly, would have lower large values.

So, you are right on all of them. All of them are O (n ^ 2). This is one of the reasons that the tape went the way of dinosaurs to active work. For backup, they are still used in some places, but this is because they are still only O (n) for linear storage.