CODEWITHSUNDEEP
algorithmcomplexity-theorybig-oanalysis
user2067259
user2067259

Reputation: 1

GCD - Euclid's algorithm and Factorization Algorithm Analysis

As I'm preparing for my introduction to algorithms class midterm, I am going though some previous tests the professor posted and I found this question:

Calculate gcd(312,455) two ways: by finding the factorization of each number, and by using Euclid's algorithm. What is the complexity of each approach?

His answer was:

gcd(455,312) = gcd(312,143) = gcd(143,26) = gcd(26,13) = gcd(13,0) = 13

factors(312)= {2, 3, 13} factors(455)= {5, 7, 13}

Complexities:

How did he arrive to the complexities?

Upvotes: 0

Views: 1496

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

To analyze Euclidean GCD, you have to opt for worst case values to do so: I personally found that Fibonacci pairs are the most suitable for this matter. E.g.

EGCD(121393, 75025) = 1; // With 24 iterations (or recursive calls).

Take a look at this "sequence":

enter image description here

With fibonacci pairs, we notice that:

121393 % 75025 == 121393 - 75025 == 46368.

Therefore, there is a decreasing factor of 121393 / 46368 = **2.61** (more or less);

Definitely, the worst case running time would make use of Small Oh Notation, since best cases would take Omega(1), in other words Constant Time, when, for instance, the dividend is 1000 and the divisor is 2.

Since we have a decreasing factor, we are allowed to put the recurrence relation like the following:

enter image description here

You have to be aware that this running time is applicable exactly the same way for the iterative version of the EGCD algorithm.

Upvotes: 1

coproc
coproc

Reputation: 6257

The given complexities are rough worst case bounds for the number of needed arithmetic operations:

  • Euclidean algorithm: For a >= b we have gcd(a,b) = gcd(b, a mod b) where min(b, a mod b) < a/2, so after at most two reduction steps we have at least a reduction of the first operand by 1/2. So the number of reduction steps is bound by the logarithm of a with basis sqrt(2) which is c * log(a) for some constant c.

  • factorization: For testing primality of a number or factorizing the square of a prime it suffices to check the factors up to the numbers square root. If the given number has smaller factors then we need even less divisibility tests. So the number of needed divisions is easily bound by sqrt(a)+sqrt(b). Since there can be at most ld(a) factors of a and ld(a) < sqrt(a) the remaining comparisons and multiplications to get the gcd are also bound by sqrt(a).

Upvotes: 0

Related Questions