1

Here n>m. I have analyzed the worst case when n = fibonacci Nth term and m = fiboncci (N-1)th term.In this case total work will be proportinal to N or time complexity will be O(N).But I am interested in finding time complexity(theta notation) in terms of n.But I am not getting how to find relation between n and N or the upper and lower bound in terms of n.

int gcd(int n, int m) {
        if (n%m ==0) return m;
        if (n < m) swap(n, m);
        while (m > 0) {
            n = n%m;
            swap(n, m);
        }
        return n;
}

Please help.

cryptomanic
  • 5,986
  • 3
  • 18
  • 30

2 Answers2

0

I would try to analyse how m changes after two iterations of the loop. One iteration might change n very little, for example (1001, 1000) -> (1000, 1). m might also change very little, for example (1999, 1000) -> (1000, 999). So analysing how either changes in a single iteration gives you very little. However, if you have two iterations then you will always have a big change.

So analyse this: If r = n/m, how does m change after two iterations of the algorithm, depending on r? By which factor does it decrease at least? (By the way, what is r for Fibonacci numbers? Does that explain the worst case? )

gnasher729
  • 51,477
  • 5
  • 75
  • 98
0

You might find this interesting.

It tries to explain Lamé's theorem for the number of steps of the GCD algorithm. The worst case is when the 2 numbers are consecutive Fibonacci numbers.

Matrix
  • 1,810
  • 1
  • 19
  • 20