Prashnikaप्रश्निका
Code
About
‹ Back to the paper

Question 41

1 mark

Computer ScienceISC Computer Science - Competency Focused Practice Questions (CISCE, August 2024)Short answerComplexity and Big O notation

Answer the following question.

“Finding the greatest common divisor (GCD) of two positive integers results in the time complexity…

“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.
Read the note: ISC Practicals and Theory - GCD

Answer

Answer

The GCD (by Euclid's algorithm) is found by repeatedly replacing the larger number with the remainder of dividing it by the smaller one. Each such step reduces the larger number to less than half its previous value within at most two steps, so the number of steps needed is proportional to $\log N$, giving a time complexity of $O(\log N)$.