Recall the conversion from a k$-$tape machine to a single tape machine.

The contents of the single tape machine are the concatenated contents

of the k tapes, separated by #$.$ For each transition in the k$-$tape

machine, the single tape machine takes the following steps:

$$ Scan entire tape, keeping track of the symbols that each tape head

points to

$$ Scan back to the beginning of the tape

$$ Scan the tape again, modifying the contents of each tape head

location to reflect the k$-$tape machine$$s transition

$$ Scan back to the beginning of the tape

Thus, the entire tape is scanned twice in each direction to simulate a

single transition of the k$-$tape machine.

Assume the k$-$tape machine takes t$($n$)>=$ n time $$ i$.$e$.,$ for an input of

length n$,$ the k tape machine takes at most t$($n$)$ steps. Your goal is

to find the runtime of the single tape machine. For this analysis, k is

assumed to be a constant.

Let M$\_$k be the k$-$tape machine and M$\_1$ be the single tape machine that

simulates Mk$$s behavior.

$5$ points For an input w of length n$,$ what is the maximum number

of symbols on any of the tapes of M$\_$k when computing w$?$

$5$ points What is the maximum number of steps M$\_1$ takes to simu$-$

late any single transition of M$\_$k$?($Use the answer to the previous

question.$)$

$5$ points What is M$\_1$s runtime? $($Use O notation and ignore con$-$

stant multiples.$)$ PLS HELP i will upvote!!!