In function gcd(m,n), each iteration of while loop has one test condition, one division

and two assignment that will take constant time. Hence number of times while loop

will execute will determine the complexity of the algorithm. Here it can be observed

that in subsequent steps, remainder in each step is smaller than its divisor i.e smaller

than previous divisor. The division process will definitely terminate after certain

number of steps or until remainder becomes 0.

**Best Case**

If m=n then there will be only one iteration and it will take constant time i.e O(1)

**Worst Case**

If n=1 then there will be m iterations and complexity will be O(m)

If m=1 then there will be n iterations and complexity will be O(n)

**Average Case**

By Euclid‟s algorithm it is observed that GCD(m,n) = GCD(n,m mod n) = GCD(m mod n, n mod (m mod n))

Since m mod n = r such that m = nq + r, it follows that r < n, so m > 2r. So after every two iterations, the larger number is reduced by at least a factor of 2 so there are at most O(log n) iterations.

Complexity will be O(log n), where n is either the larger or the smaller number.

## 0 टिप्पणियाँ:

## Post a Comment