###### Computer-Networks

October 25, 2023###### Research Aptitude

October 25, 2023# GATE 2007

Question 44 |

In the following C function, let n >= m.

int gcd(n,m) { if (n%m ==0) return m; n = n%m; return gcd(m,n); }

How many recursive calls are made by this function?

θ (log _{2} n) | |

Ω (n) | |

θ (log _{2}log_{2} n)
| |

θ(√n) |

Question 44 Explanation:

The given code is to calculate the greatest common divisor (GCD) using Euclidean algorithm.

Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)

Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)

Correct Answer: A

Question 44 Explanation:

The given code is to calculate the greatest common divisor (GCD) using Euclidean algorithm.

Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)

Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)

Subscribe

Login

0 Comments