‹ 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.
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)$.