64 votes 64 votes In the following C function, let $n \geq 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? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$ Algorithms gatecse-2007 algorithms recursion time-complexity normal + – Kathleen asked Sep 21, 2014 • retagged Jun 30, 2017 by Silpa Kathleen 26.7k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply dhingrak commented Dec 2, 2014 reply Follow Share Plz explain how to solve this problem...? 0 votes 0 votes Nit9 commented Jan 18, 2017 reply Follow Share http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/ 0 votes 0 votes asriv commented Jun 2, 2017 reply Follow Share This is an implementation of the euclid's algorithm for finding the greatest common divisor. This link talks about the analysis of the euclid's algorithm. Hope you may find it a bit enlightening. https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm 0 votes 0 votes sunil sarode commented Jun 18, 2017 reply Follow Share https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm 1 votes 1 votes Prakhar Garg commented Mar 18, 2019 reply Follow Share For m=2 and for all n=2^i , running time is ϴ(1) which will contradicts every option... 1 votes 1 votes rohith1001 commented Dec 20, 2019 reply Follow Share https://stackoverflow.com/a/30687762/5982032 0 votes 0 votes Please log in or register to add a comment.
Best answer 63 votes 63 votes Worst case will arise when both $n$ and $m$ are consecutive Fibonacci numbers. $\text{gcd}(F_n, F_{n-1}) = \text{gcd}(F_{n-1},F_{n-2}) = \dots = \text{gcd}(F_1,F_0) = 1$ and $n^{th}$ Fibonacci number is $1.618^n$, where $1.618$ is the Golden ratio. So, to find $\text{gcd} (n,m)$, number of recursive calls will be $\Theta (\log n) $. Correct Answer: $A$ Vikrant Singh answered Dec 15, 2014 • edited Apr 29, 2019 by Naveen Kumar 3 Vikrant Singh comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments register_user_19 commented Oct 30, 2019 reply Follow Share good to read http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html - fibonacci series, got lot of properties (last digit, last 2 digit periodic etc) -cormen 3rd ed pg 59, ex pg 108 (3rd ed), ch27 pg 776 (3rd given TC for finding ith fib number), pg 993 (given gcd has worst case when n , m are consecutive fibonacci number) 1 votes 1 votes Nikhil555555 commented Aug 8, 2020 reply Follow Share worst question by gate , i think this questions are made to leave or else you are going to lose your precious time!!!! 8 votes 8 votes gatecse commented Aug 8, 2020 reply Follow Share Yes, if you don't have sufficient background knowledge you'll lose time on such questions. 6 votes 6 votes Please log in or register to add a comment.
28 votes 28 votes Try to put input in worst case... Mostafize Mondal answered Aug 16, 2018 • edited Oct 30, 2018 by Mostafize Mondal Mostafize Mondal comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments ankit3009 commented Jan 14, 2021 reply Follow Share Bhai, please explain @himanshu 0 votes 0 votes svas7246 commented Jan 27, 2021 reply Follow Share @ankit3009 n is approaching 1 function call by function call that is we are dividing it through by 2 plot the function calls and you can observe it takessome k function calls those are (n/2 power k )=1 equating it we will get logn 1 votes 1 votes anshik1998 commented Feb 5, 2021 reply Follow Share @ankit3009, take the worst case input like 97, 48 or whatever you wish. And, do consider this fact (bolded): int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } Give a shot, and still if you can't get, revert back with issue, more specifically where you're stuck on. 1 votes 1 votes Please log in or register to add a comment.
13 votes 13 votes This is how I approached the Problem. Bodhisattwa answered Aug 21, 2020 Bodhisattwa comment Share Follow See all 2 Comments See all 2 2 Comments reply satya753 commented Nov 21, 2020 reply Follow Share Wait a minute! 0 votes 0 votes venkat srinath commented Aug 9, 2023 reply Follow Share how have u got this idea in the exam man😢 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes let T(m,n) be the total number of steps. so, T(m,0) = 0, T(m,n) = T(n, m mod n) on average => $T(n) = \sum :{T(k,n)} from k=0 to n$ by using masters theorem you will get: $ \approx \Theta (\log n)$ Nit9 answered Oct 6, 2015 Nit9 comment Share Follow See 1 comment See all 1 1 comment reply gautamcse27 commented Sep 2, 2016 reply Follow Share How to solve by simple way by applying recurrence relation? 0 votes 0 votes Please log in or register to add a comment.