Computer-Networks
October 25, 2023Research Aptitude
October 25, 2023GATE 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?
| θ (log2 n) | |
| Ω (n) | |
| θ (log2log2 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)