Recursive Relations

Question

I've been doing recursive relations and found a question I wasn't able to solve. I'm given a recursive algorithm that finds the $\gcd$ of two numbers $p$ and $q$.

Algorithm:

function GCD(p,q)
    if (q == 0) then
        return p;
    else
        return GCD(q, p mod q)

Now in the question they have stated that the worst case input of this algorithm would be $p = fib(n)$ , $q = fib(n-1)$. And then we have to analyze the running time complexity of this algorithm.

Now I know how to compute the running time of recursive algorithms but I don't know how to break this GCD ($p$ , $p$ mod $q$).

I tried to calculate.

If $p = fib(n)$ and $q = fib(n-1)$ -> GCD $(fib (n-1), fib (n-2))$ but then this keeps doing on and on. How can I break this down?

Answer 1

You are counting down the Fibonacci numbers, which will end when you get to zero. If $p=fib(n)$, it will take $n$ trips through your algorithm. Binet's formula lets you compute $n$ from $fib(n)$