So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM?
I just don't know where to get started...
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityMulti-tape Turing Machine running in $O(f(n))$ can be simulated by a single-tape Turing machine running in $O(f^2(n))$.
Try writing a single-tape Turing machine that stores symbols from your $3$ tapes on its one tape, separated by some unique symbol not in $\Sigma$.
hint: For every step of your $k$-tape machine, a one-tape machine must first do at most $k\cdot n$ steps to find the position.