Time complexity of $L=\{a^nb^n | n \ge 1\}$
If I correclty understand the algorithm, your TM starts &quot;marking&quot; 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&gt;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&gt;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&gt; h}
$$
on the constraint $h+k+j=n$, $j&gt;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.

If you want to play with your TM and see the exact number of transitions, go here, compile and load a word, enjoy!