retagged by
337 views
1 votes
1 votes

retagged by

1 Answer

Best answer
2 votes
2 votes

Proceed according to Algorithm

I am taking an examples here :

example : 

consider m=13 , n=17 , Now

Both IF conditions are false so directly go to while loop here (m>0)

1) n= 17 % 13 = 4

   After Swap(4 , 13) the values will be m = 4 and n = 13 ...(m>0)

2) n= 13 % 4 = 1

  After Swap(1 , 4) the values will be m = 1 and n = 4...(m>0)

3) n= 4 % 1 =0

  After Swap(0 , 1) the values will be m = 1 and n = 0...(m>0)

4)) n= 0 % 1 = 1

Now you can see 4 iterations have been performed to reach the end. Here i have taken n = 17

So as n=17 has taken 4 iterations so COMPLEXITY WILL BE O(log n)  as log 17 is approx equal to 4.

Now you can take any values for m and n you will get COMPLEXITY O(log n) assuming worst case only.

selected by

Related questions

1 votes
1 votes
1 answer
2