2

The following is an iterative implementation of the Euclidean algorithm for computing the greatest common divisor of m and n.

while (m != n) 

    { 

        if (m > n) 

            m = m - n; 

        else

            n = n - m; 

    }

What is the time complexity of the above code?

kaya3
  • 47,440
  • 4
  • 68
  • 97
Gaurav Arora
  • 21
  • 2

2 Answers2

0

Worst case is at least linear in n + m (hence exponential in the size of input) since we can choose m > 1 and n = 1 so that this algorithm correctly determines GCD(m, n) = 1 in exactly m - 1 iterations. This means the worst case is Omega(m + n) = Omega(2^k), where k is the number of bits in the encoding of the input.

Worst case is at most linear in m + n (hence exponential in the size of input) since at each step either m or n is reduced by at least 1 (assuming n, m > 0). Thus the loop can iterate at most m + n times (in fact, it will never iterate that many times, but it certainly doesn't iterate more). This means the worst case is O(m+n) = O(2^k), where k is the number of bits in the encoding of the input.

Thus, the worst case is exactly linear in m+n, that is, exponential in the size of the input k: it is Theta(m+n) = Theta(2^k).

When an algorithm which takes numbers as input has a runtime which is polynomial in terms of the values of the inputs, but exponential in terms of the size of the input's encoding (e.g., binary), the algorithm is said to run in pseudopolynomial time.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • I think you are using 'n' here to mean two different things; in your first example you said n = 1 and then that it does n - 1 iterations. – kaya3 Jan 28 '20 at 20:25
  • @kaya3 You're right, should be m - 1 by the looks of it. Probably also confusing if I use O(n) etc. as a synonym for linear in this case. – Patrick87 Jan 28 '20 at 23:02
0

Here the inputs are the numbers n and m of size log2(n) and log2(m), respectively. Time complexity is expressed as a function of the input size.
In general, time complexity of the Euclidean algorithm is linear in the input size (check this answer for an example), but with this implementation you have an exponential worst case runtime.

Assume n>m and m=1. This means that the code becomes the following:

while (m != n) 
    { 
        n = n - m; 
    }

In the worst case you have a number of iterations equals to n, a number exponential in the input size.

abc
  • 11,579
  • 2
  • 26
  • 51
  • Better answer than mine. The input size really is the number of bits, not the value of the numbers input. It's only pseudopolynomial. – Patrick87 Jan 29 '20 at 00:32