How can I improve bound for Euclid's GCD calculation function? If $a > b \ge 0$ the call $Euclid(a, b)$ makes at most $1 + \log b$ recursive calls. How can I improve this bound to $1 + \log(b/\gcd(a,b))$?
the pseudocode is following:
Euclid(a,b)
 if b==0
  return a
 else return Euclid(b, a mod b)

So the recurrence relation is:
$T(n) = 1$ when $b=0$ and $T(n/b) + O(1)$ when $a > b > 0$.
Here, $a = 1, b = b, f(n) = O(1)$. Using the master theorem,
$f(n) = O(1)$, which is $O(n^{log_b1}) = O(n^0) = O(1)$. So, $T(n) = O(\log b)$.
But how can it be improved to $\log(b/\gcd(a,b))$?
 A: Well, first of all, you haven't even shown that there are at most $1 + \log b$ recursive calls; you've only shown that there are $O(\log b)$, which is at the very least not as precise as what you're going for. 
Although, $1+\log b$ is false if the logarithm is binary: $\gcd(F_{n+2}, F_{n+1})$ takes $n$ recursive calls to compute, which is approximately $\log_\phi b$, where $\phi = \frac{1+\sqrt{5}}{2}$, or about $1.44 \log_2 b$. You can inductively prove that if $n$ recursive calls are required, then $b \ge F_{n+1}$ and $a \ge F_{n+2}$, so that this is the worst case.
Anyway, if you want to improve a bound of $O(\log b)$ to $O(\log \frac{b}{\gcd(a,b)})$, or $1.44\log_2 b$ to $1.44 \log_2 \frac{b}{\gcd(a,b)}$, or whatever, then let $a' = \frac{a}{\gcd(a,b)}$ and $b' = \frac{b}{\gcd(a,b)}$, and note that computing $\gcd(a',b')$ takes exactly the same amount of time as computing $\gcd(a,b)$ in exactly the same steps. For example:


*

*$\gcd(800,300) = \gcd(300, 200) = \gcd(200,100) = \gcd(100,0) = 100$.

*$\gcd(8,3) = \gcd(3,2) = \gcd(2,1) = \gcd(1,0) = 1$.


So actually, better bounds like $O(\log b') = O(\log \frac{b}{\gcd(a,b)})$ or $1.44 \log_2 b' = 1.44 \log_2 \frac{b}{\gcd(a,b)}$ or whatever bounds you have on how long it takes to compute $\gcd(a',b')$ are also valid bounds on how long it takes to compute $\gcd(a,b)$. 
