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

Question

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?

Answer 1

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$.