1
$\begingroup$

In the textbook by Arora and Barak in Chapter 1 and section 1.7 they have proved how a UTM can do simulation in $O(T \log T)$ time. I have read it and understood everything except that how the $k$th shift can cost just $O(2^k)$ time. One can read the proof for complete details but I can explain my doubt as the following problem.

Assume a TM tape divided into blocks where for $i \geq 0$ the $i$th block contains $2^i$ cells. Further, assume that the $k$th block is full i.e. all $2^k$ cells in that block have some symbol of the alphabet and for all $0 \leq i < k$, the $i$th block is empty i.e. they have no symbols. Now, we need to take first $2^{k-1}$ symbols present in $k$th block and put the left most in first block, then start putting rest of the symbols in sequence by filling first half of every $i$th block for $i < k$. One can check that we have exactly that many symbols to place in lower indices block's first half.

The book say that it can be done in $O(2^k)$ time, which I am not able to prove.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.