# Time complexity of $L=\{a^nb^n | n \ge 1\}$

Consider the following language:

$$L=\{a^nb^n | n \ge 1\}$$

I constructed the following Turing Machine:

$$\begin{eqnarray} T &=& (Q, \Sigma, \Gamma, \delta, q_0, B, F) \nonumber \\ Q &=& \{q_0, q_1, q_2, q_3, q_4\} \nonumber \\ \Sigma &=& \{a, b\} \nonumber \\ \Gamma &=& \{a, b, X, Y, B\} \nonumber \\ F &=& \{q_4\} \nonumber \end{eqnarray}$$

When the input comes as $$aabb$$, the Turing Machine works like this:

How can you know the time complexity of this Turing Machine?

• "how it works" does not mean the transition diagram… I meant describe the steps with words in english. Apr 25 at 10:37
• @Nathaniel I editted it. Apr 25 at 11:04

If I correclty understand the algorithm, your TM starts "marking" the first $$a$$, then it finds the first $$b$$ and marks it, then it comes back the the first unmarked $$a$$ and so on. So, assuming that you have in input a string $$w$$ of lenght $$n$$ that belongs to the language $$L$$, you have $$\frac{n}{2}$$ $$a$$'s that have to match with the same number of $$b$$, each $$a$$ is paired to a $$b$$ that is $$\frac{n}{2}$$ cells away, so to perform a complete matching you need $$\frac{n}{2}$$ transitions from an $$a$$ to reach the $$b$$ to be coupled with it, and again $$\frac{n}{2}$$ transitions to reach the next $$a$$, so in total $$n\cdot \frac{n}{2}$$ transitions (actually, you have to perform an extra transition for each letter to put the head in the right place, so the exact amount of transitions is $$\frac{n^2}{2}+n+1=O(n^2)$$).
Now, let us consider a word $$w$$ of lenght $$n$$ that does not belong to the language $$L$$. If it start with $$b$$, it is immediately rejected, so suppose $$w=a^hb^kv$$, where $$v\in a\Sigma^*$$ has lenght $$j>0$$ and $$h+k+j=n$$. If $$k\leq h$$, then the TM will performs $$\frac{k^2}{2}+k+1$$ transitions before stopping (and rejecting $$w$$), while if $$k>h$$, then it will make $$\frac{h^2}{2}+h+1$$ transitions. So, the worst case correspond to the maximum of the function $$f(h,k,j)=\cases{\frac{k^2}{2}+k+1, \quad k\leq h\\ \frac{h^2}{2}+h+1,\quad k> h}$$ on the constraint $$h+k+j=n$$, $$j>0$$, and it is not difficult to see that it is reached for $$|h-k|=1$$ and $$j=1$$.
Summing up: the worst case is reached when $$w$$ belongs to the language $$L$$, and the TM must carry out $$O(|w|^2)$$ transitions.
• So the time complexity is $\Theta(n^2)$. It is also $O(n^3)$, $\Omega(n)$, and so on. Apr 26 at 14:45