What is the $\mathcal O$ of subtraction-based GCD algorithm?
Suppose that $a,b$ are the two input numbers. At each step of the algorithm, the sum $a+b$ decreases, since (assuming $a &gt; b$), the new numbers are $a'=a-b,b'=b$, and $a'+b'=a &lt; a+b$ (since we stop when $b=0$). Thus the algorithm terminates in at most $a+b$ steps. This is almost tight: if $b = 1$, then the algorithm terminates in $a$ steps.

Summarizing, on inputs $a,b$, the number of steps (or arithmetic operations) is at most $a+b$, and could be as bad as $a$. In terms of the length $n$ of the input (number of bits needed to represent it), the number of operations is at most $O(2^n)$ (since $a,b \leq 2^n$), and could be as bad as $\Omega(2^n)$ (when $a = 2^n,b=1$). Thus the worst-case running time (as measured by number of steps) is $\Theta(2^n)$, where $n$ is the input length.