O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”?

Question

I need to build a TM with exactly 1 tape for the language L = {w| w is a word with same number of a's and b's in it, for example: abba, aababb}

The TM has to have ONLY 1 tape and it has to run in O(nlog(n)) time. I understand how to do it in O(n^2) but i have no idea how to make it nlog(n).

If i have the input w = "aaaa....abbbbb....bb" for example, where w = a ^ n/2 * b ^n/2 (which is the worst case) then i will go backwards each time (to delete each a for each b) and the steps taken will be of size 1,2,3,4.....n. Sum(1 to n) is O(n^2)...

Help ? any ideas ?

Answer 1

The idea is to repeatedly apply the following algorithm:

1. Determine the parity of the number of $a$'s, deleting every second $a$ on the way.
2. Determine the parity of the number of $b$'s, deleting every second $b$ on the way.
3. Accept if there were no $a$'s or $b$'s.
4. Reject if the parities are different.
5. Jump back to Step 1.

Each phase of the algorithm takes $O(n)$ steps, and there are $O(\log n)$ phases, for a total of $O(n\log n)$.

As an aside, using crossing sequences you can prove a matching lower bound of $\Omega(n\log n)$. Consider all inputs of the form $a^ib^{n-i} a^nb^n b^ja^{n-j}$. Such an input should be accepted iff $i = j$. For every input $x$, trace the execution of the Turing machine. When it crosses from the $n$th letter to the $(n+1)$th letter, record the state $\sigma$ of the Turing machine, and wait until the Turing machine crosses from the $2n$th letter to the $(2n+1)$th letter, at which time add $\sigma$ to the crossing sequence, and go back to waiting for it to cross from the $n$th letter to the $(n+1)$th letter. A cut-and-paste argument shows that the crossing sequence must depend on $i$, and so must be of length $\Omega(\log n)$ in the worst case, where the hidden constant depends on the number of states in the machine. Since it takes the machine $n$ steps to add a state to the crossing sequence, we obtain a lower bound of $\Omega(n \log n)$.