[Solved]: How do we determine how much time a multi-tape DTM saves over a one-tape DTM?

Problem Detail: 

Note: This is a part of a homework question

Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$}

Then it says "Discuss how much time your machines saves over a one-tape DTM using the same algorithm" Any hint?

Here's my algorithm:

(1) Cut-and-paste c's to tape 3

(2) Cut-and-paste b's to tape 2

(3) Cross out each triplets, accept if last round cuts all three, reject if there's leftover

Which seems like it has a time complexity of $O(n+n+3n)=O(5n)$ Then how do we determine the time complexity for the one-tape version?

Asked By : Iancovici

Answered By : Iancovici

Figured it out. Turns out a theorem states that

For any multi-tape DTM $M$, there exists a two-way, one-tape DTM $M_1$ computing the same function s.t. for all inputs $x$, $Time_{M_1}(x) \leq c \centerdot (Time_M(x))^2$

Reference: Du, Dingzhu, and Ker Ko. Problem solving in automata, languages, and complexity. New York: Wiley, 2001. Print.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11053