How the time complexity of gcd is Θ(logn)?

Question

I was solving a time-complexity question on Interview Bit as given in the below image.

The answer given is Θ(theta)(logn) and I am not able to grasp how the logn term arrive here in the time complexity of this program.

Can someone please explain how the answer is theta of logn?

Answer 1

Theorem given any x, gcd(n, m) where n < fib(x) is recursive called equal or less than x times.

Note: fib(x) is fibonacci(x), where fib(x) = fib(x-1) + fib(x-2)

Prove

Basis

every n <= fib(1), gcd(n, m) is gcd(1,m) only recursive once

Inductive step

assume the theorem is hold for every number less than x, which means:

calls(gcd(n, m)) <= x for every n <= fib(x)

consider n where n <= fib(x+1)

if m > fib(x)

   calls(gcd(n, m))
=  calls(gcd(m, (n-m))) + 1
=  calls(gcd(n-m, m%(n-m))) + 2  because n - m <= fib(x-1)
<= x - 1 + 2
=  x + 1

if m <= fib(x)

   calls(gcd(n, m))
=  calls(gcd(m, (n%m))) + 1  because m <= fib(x)
<= x + 1

So the theorem also holds for x + 1, as mathematical induction, the theorem holds for every x.

Conclusion

gcd(n,m) is Θ(reverse fib) which is Θ(logn)