Time complexity of following function

Question

In the following C++ function, let n >= m.

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

What is the time complexity of the above function assuming n > m? Answer to this question is O(log n), but I am not getting how it is calculated?

@TimBiegeleisen swap is just a normal function to swap values — dexter, Aug 22 '16 at 05:48
@dexter Thanks...I have suspected this but as I'm not a C++ person I asked. — Tim Biegeleisen, Aug 22 '16 at 05:50

Peter Lawrey · Accepted Answer · 2016-08-22T05:42:05.770

3

on each iteration, the value of n reduces by a factor of the golden ratio on average. I suggest trying to work out the worst case and it should be about log base 1.618 of n

For more details https://en.wikipedia.org/wiki/Euclidean_algorithm which notes "If the Euclidean algorithm requires N steps for a pair of natural numbers a > b > 0, the smallest values of a and b for which this is true are the Fibonacci numbers F(N+2) and F(N+1), respectively."

e.g. If you start with Fib(n+2) and Fib(n+1) you will get Fib(n) and Fib(n+1) on the next iteration until you stop at 1.

edited Aug 22 '16 at 05:42

answered Aug 22 '16 at 05:37

Peter Lawrey

525,659
79
751
1,130

sorry I didn't get it. How am I supposed to think about using fibonacci on seeing above function? – dexter Aug 22 '16 at 07:16
1

@dexter In the worst case you have two Fibonacci numbers e.g. 21 and 13, when you do 21 % 13 you get 8 which is the previous fibonacci number, 13 % 8 is 5, the previous one, 8 % 5 is 3 the previous one and 5 % 3 = 2 finally 3 % 2 == 1. – Peter Lawrey Aug 22 '16 at 08:07

Raman Sahasi · Answer 2 · 2016-08-22T05:52:16.727

First consider these two possibilities for while loop:

In the loop given below, the complexity of this loop is O(n) because the algorithm grows in proportion to its input n:
```
while (n > 0) {
    n = n-1;
    ...
}
```
Whereas in the loop given below, since there's a nested loop, the time would be O(n^2).
```
while(n>0) {
    n = n-1;
    while(m>0) {
        m = m-1;
        ...
    }
}
```
However, in the algorithm which you've provided, you aren't traversing the loop for every m or n; instead, you are simply using divide-and-conquer approach, and you're exploring only portion of entire n in your loop. On each iteration, the value of n isn't reducing by just a factor of 1, but a bigger ratio:
```
while (m > 0) {
    n = n%m;
    swap(n, m);
}
```

Time complexity of following function

2 Answers2