Consider the following language: $$L = \{a^nb^{n^2} \mid n≥1\}\,$$

When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, and the second one to repeat $n$ times the count of $n$. Thus, because of the way we’re using the second tape, it should have a $\Theta(n^2)$ space complexity, and I would say the same concerning the time one. I thought it was correct, but the solution is $TM(x)=|x|+n+2$, where, $x$ is, supposedly, the length of the string, hence $\Theta(|x|)$. It seems correct to me, so is my reasoning completely wrong, or just a different way to express it?

Could we have reasoned about it differently, and say, for example, for every $a$ we write down a symbol on the first tape, and then count the $b$'s, by scanning the symbols back and forth $n$ times? This time, the space complexity should just be $\Theta(n)$, while the time complexity should remain unchanged. What would change if we had a single-tape TM?


Your confusion stems from a double use of $n$. Let's write $L$ differently: $$ L = \{ a^i b^{n-i} : n-i = i^2, i \geq 1 \}. $$ Here $n$ is the input length. It should be clear that the space complexity is $O(n)$.

Your first estimate just translates to a space complexity of $O(i^2) = O(n)$, since $n = i^2 + i$.

| cite | improve this answer | |
  • $\begingroup$ Oh, that's right. Is the second way of using the TM valid, by the way? It still $\in \Theta(n)$, but just asking. $\endgroup$ – Antonio Frighetto Jan 15 '19 at 16:58
  • $\begingroup$ There are many solutions that have space complexity $\Theta(n)$. In fact, if you don't count the space on the input tape, then you should be able to make do with only $\Theta(\log n)$ space. $\endgroup$ – Yuval Filmus Jan 15 '19 at 17:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.