McqMate

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) |

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. |

1.4k

0

Do you find this helpful?

17

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?
- Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
- Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?
- If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?
- What is the GCD of a and b?
- Who gave the expression for the probability and expected value of gcd?
- Which of the following is also known as GCD?
- In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?
- What is the GCD according to the given Venn Diagram?
- What is the GCD of 48, 18, 0?