# Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$

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$$.
• Oh, that's right. Is the second way of using the TM valid, by the way? It still $\in \Theta(n)$, but just asking. – Antonio Frighetto Jan 15 '19 at 16:58
• 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. – Yuval Filmus Jan 15 '19 at 17:22