✏️ Explanatory Question

[Computational Complexity and Big-O Notation]

Question:

Finding the greatest common divisor (GCD) of two positive integers results in the time complexity of O(log N), where N is the larger number of two inputs. Justify the statement.

👁 0 Views
📘 Detailed Answer
🟢 Easy
← Previous Question: A student had written the following method to display “Hello World” four times: void displayMessage() { System.out.println("Hello World"); System.out.println("Hello World"); System.out.println("Hello World"); System.out.println("Hello World"); } Later, the student modified the code using a loop: void displayMessage() { int i = 1; while(i
💡

Answer with Explanation

Answer:

The statement is correct. The time complexity of finding GCD is O(log N) because it uses the Euclidean Algorithm, which repeatedly reduces the problem size.

Explanation:

The Euclidean Algorithm works as follows: 

gcd(a, b) = gcd(b, a % b)

In each step:

  • The larger number is replaced by the remainder of division
  • The values decrease rapidly

This reduction happens logarithmically. That means:

  • The number of steps required is proportional to log N
  • N is the larger of the two numbers

For example: 

gcd(48, 18)
→ gcd(18, 12)
→ gcd(12, 6)
→ gcd(6, 0)

Here, the numbers reduce quickly in very few steps.

Conclusion:

  • Each step reduces the problem size significantly
  • The total number of steps is proportional to log N
  • Therefore, time complexity = O(log N)
← Previous Question: A student had written the following method to display “Hello World” four times: void displayMessage() { System.out.println("Hello World"); System.out.println("Hello World"); System.out.println("Hello World"); System.out.println("Hello World"); } Later, the student modified the code using a loop: void displayMessage() { int i = 1; while(i