Q. What is the computational complexity of Binary GCD algorithm where a and b are integers?

(A) o (log a + log b)2)
(B) o (log (a + b))
(C) o (log ab)
(D) o (log a-b)

💬 Discuss

✅ Correct Answer: (A) o (log a + log b)2)

Explanation: from the binary gcd algorithm, it is found that the computational complexity is o (log a + log b)2) as the total number of steps in the execution is at most the total sum of number of bits of a and b.

Published by Mr. Dubey ⭐ 104.82K Points at 16-Sep-2023 03:43 pm in Design and Analysis of Algorithms

Explanation by: Mr. Dubey

from the binary gcd algorithm, it is found that the computational complexity is o (log a + log b)2) as the total number of steps in the execution is at most the total sum of number of bits of a and b.

💬 Discussion

📊 Question Analytics

👁️

108

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

97%

Success Rate

Q. What is the computational complexity of Binary GCD algorithm where a and b are integers?

Explanation by: Mr. Dubey

💬 Discussion

Related MCQs

📊 Question Analytics