0

What will be run-time analysis in terms Big O?

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;
}

The answer given is O(log N). But I'm not able to figure out solution. Can anyone plz? Thanks in advance.

PS: I know lots of people are saying this is a duplicate problem and see posted solution earlier. Well, I got the solution even before posting here. I asked for a "SIMPLE" explanation to such solutions.

Nuance
  • 101
  • 2
  • 14
  • check this answer https://stackoverflow.com/a/3981010/3940445 – CJR Jul 01 '17 at 10:33
  • More explained in details answer could be found here: https://softwareengineering.stackexchange.com/questions/212719/what-is-the-big-o-cpu-time-of-euclids-algorithm-of-greatest-common-divisor-of – Artem Barger Jul 01 '17 at 10:33
  • Always good searching for similar questions before posting yours. Can save tonnes of time :) – sjsam Jul 01 '17 at 10:42

0 Answers0