top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

What is time complexity of euclidean method to find GCD?

+2 votes
389 views

Please explain step by step

posted Dec 10, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

At some point, you have the numbers (a,b) with a>b. After the first step these turn to (b,c) with c=amodb, and after the second step the two numbers will be (c,d) with d=bmodc.

Now think backwards. As d=bmodc, we know that b=kc+d for some k>0. The smallest possibility is k=1, therefore b≥1c+d=c+d.

From that result and from a>b we get a>c+d. If we add the last two inequalities we just derived, we get that (a+b)>2(c+d).
In words, after each two consecutive steps the sum of the two numbers decreases to less than half of its original size.

Now look at the very first step of the algorithm. At the beginning, we have some (a,b) with a>b. After the very first step we have (b,c) with c=amodb, and clearly b>c. Hence, after the very first step both numbers are at most equal to the smaller of the two input numbers.

Putting those two results together, we may conclude that the number of iterations (recursive calls in other implementations) is at most logarithmic in the smaller input number. In other words, the number of iterations is at most linear in the number of digits in the smaller input number.

To see that this analysis is asymptotically optimal, take (a,b)=(Fn+1,Fn) -- that is, two consecutive Fibonacci numbers.

answer Dec 11, 2015 by Shivaranjini
0 votes

Iterative Algo

function gcd(a, b)
    while b ≠ 0
       t := b; 
       b := a mod b; 
       a := t; 
    return a; 

Recursive Algo

function gcd(a, b)
    while a ≠ b 
        if a > b
           a := a − b; 
        else
           b := b − a; 
    return a; 

Time Complexity
Base Case
O(1) --- (algo executed in single step)

Worst Case
O(h) i.e. O(log b), where h is the number of digits in the smaller number i.e. b

Average Case
[12/π^2]*log2loga+O(1) -- (Source: Wikipedia)

answer Dec 11, 2015 by Mishthy Mukherjee
Similar Questions
+2 votes

Say we only know the worst case and best case complexity of an algo (Algo is not known). Is it possible to get the average case complexity?

+3 votes

In an "N" element integer sorted array, a particular elements is repeating "(N/2)+1" times. How much time it take to find the repeating element.

+2 votes

Assume priority queue in Dijkstra’s algorithm is implemented using a sorted link list and graph G (V, E) is represented using adjacency matrix.

What is the time complexity of Dijkstra’s algorithm (Assume graph is connected)?

...