Single tape TM that converts numbers from binary notation to unary
As you have said, there are $2^n-1$ total &quot;decrements&quot;. Notice that at the $k$'th decrement, you &quot;waste&quot; $O(n)$ time on the left side, plus $O(k)$ at the right side. Sum everything up, from $k=1$ up to $k=2^n-1$:
$\sum_{k=1}^{2^n-1} n+k = n(2^n-1)+\sum_{k=1}^{2^n-1} k = n(2^n-1) + O(2^{2n})=O(2^{2n})$