2

I'm currently studying and trying to implement some algorithms. I'm trying to understand Big O notation and I can't figure out the Big O complexity for the algorithm below:

while (a != 0 && b != 0)
{
    if (a > b)
        a %= b;
    else
        b %= a;
}

if (a == 0)
    common=b;
else
    common=a;
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Tristan Demanuele
  • 301
  • 2
  • 6
  • 18

3 Answers3

6

It's easy to see that after two iterations the least of the numbers becomes at least twice smaller. If it was equal m at the beginning, then after 2K iterations it will be no more than m/2^K. If we put K = [log_2(m)] + 1 here, we'll see that after 2K iterations the least of the numbers becomes zero, and the loop terminates. Hence the number of iterations is no more than 2(log_2 m + 1) = O(log m).

adamax
  • 3,835
  • 2
  • 19
  • 21
  • It would be nice if you could also add an example of numbers that require `O(log m)` steps, to show that this bound is tight. – liori Dec 26 '10 at 21:37
  • can you add comments to the code above? so you can indicate how you can to this conclusion? – Tristan Demanuele Dec 26 '10 at 22:00
  • @tristan You mean why the minimum of the numbers decreases in this way? Suppose a > b, then after one iteration the minimum is c=a%b, and after 2 iterations it's b%c. If c <= b/2, then b%c < c <= b/2. If c > b/2, then b%c = b-c < b-b/2 = b/2. So in both cases b%c <= b/2. – adamax Dec 26 '10 at 22:21
  • @liori Yes, it was already suggested in comments, but is worth pointing out: if we take a=F_{n+1}, b=F_n, then the loop stops after (about) n iterations, and since F_n is approximately phi^n, this is our example. – adamax Dec 26 '10 at 22:24
  • I still can't understand how to calculate the complexity of the algorithm above – Tristan Demanuele Jan 03 '11 at 21:41
  • @tristan What exactly you don't understand from my answer? – adamax Jan 04 '11 at 09:14
  • i need the cost and time for every line of code. can you help? – Tristan Demanuele Jan 04 '11 at 10:17
  • Well, since the number of iterations is O(log m), the lines 1 and 3 will happen O(log m) times. And lines 4 and 6 will alternate, so each of them also happens O(log m) times. The part after the loop happens O(1) times. – adamax Jan 04 '11 at 10:49
  • and how did you come to this conclusion? – Tristan Demanuele Jan 04 '11 at 10:52
  • im not understanding from where the log m came from – Tristan Demanuele Jan 04 '11 at 10:58
  • So, we're back to the first question. What part of my answer exactly you don't understand? – adamax Jan 04 '11 at 12:27
  • i didnt understand the whole thing. What do you mean by 2K? is it a number, as in 2000? from where did you conclude m/2^K? and why did you substitute K = [log_2(m)] + 1? – Tristan Demanuele Jan 04 '11 at 13:31
  • K is an arbitrary number. If after 2 iterations the least of the numbers becomes 2 times less, then after 4 iterations it becomes 4 times less, after 6 iterations 8 times less, after 2K iterations 2^k times less. Now m / 2^K < 1 <=> K > log_2 m. Does that make sense? – adamax Jan 04 '11 at 13:54
  • so if im understanding well, the log was introduced in order to get the K subject of the formula from m/2^K? – Tristan Demanuele Jan 04 '11 at 14:41
4

That is the Euclidean algorithm for computing the greatest common divisor of two integers. I'll leave it to you to do the research on the complexity of this algorithm but the Fibonnacci numbers play an important role.

jason
  • 236,483
  • 35
  • 423
  • 525
0

Most people (who are not mathematicians) never need to find out that stuff, it's already documented: http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency

fejesjoco
  • 11,763
  • 3
  • 35
  • 65
  • Does not answer the question (which is the big-o notation for the given algorithm) (-1) – Pablo Fernandez Dec 26 '10 at 21:17
  • 1
    It does answer the question. "Euclid's algorithm grows quadratically (h2) with the average number of digits h in the initial two numbers a and b." -> O(h^2) – fejesjoco Dec 26 '10 at 21:18
  • Except if I answer this without any context, he wouldn't understand. I also won't show the entire proof. So I believe that the wikipedia article was the best possible answer. – fejesjoco Dec 26 '10 at 21:19