GCD and LCM Euclidean Algorithm in DSA C - Time & Space Complexity

Time Complexity: GCD and LCM Euclidean Algorithm

O(log min(a, b))

Understanding Time Complexity

We want to understand how fast the Euclidean algorithm finds the greatest common divisor (GCD) of two numbers.

How does the number of steps grow as the input numbers get bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}
    

This code finds the GCD of two numbers using the Euclidean algorithm and then calculates the LCM using the GCD.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop repeatedly calculates the remainder of division (a % b).
• How many times: The loop runs until the remainder becomes zero, which depends on the size of the inputs.

How Execution Grows With Input

The number of steps grows slowly compared to the size of the numbers. Each step reduces the problem size significantly.

Input Size (n)	Approx. Operations
10	Up to 5 steps
100	Up to 7 steps
1000	Up to 10 steps

Pattern observation: The steps increase slowly, roughly proportional to the number of digits, not the number itself.

Final Time Complexity

Time Complexity: O(log min(a, b))

This means the steps grow roughly with the number of digits of the smaller input, making it very efficient.

Common Mistake

[X] Wrong: "The algorithm takes time proportional to the input numbers themselves (like O(n))."

[OK] Correct: Each step reduces the numbers quickly by using remainders, so the number of steps grows much slower than the input size.

Interview Connect

Knowing the Euclidean algorithm's time complexity shows you understand efficient number operations, a useful skill in many coding problems.

Self-Check

"What if we used subtraction instead of modulo in the GCD calculation? How would the time complexity change?"