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.6k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments 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 saurabhrk commented Jan 15, 2015 reply Follow Share Plz explain, that how consecutive fibonacci numbers will give the worst case? Is there any other method to solve? 0 votes 0 votes lgau0522 commented Feb 1, 2015 reply Follow Share understanding the worst case is not the problem how the hell will we know that worst case will come for fibonacci series in GATE (under 3 min constraint) if we check manually for non-fibonacci number the answer is clearly loglog(n) 69 votes 69 votes Arjun commented May 2, 2015 reply Follow Share Some things we must know before :) 36 votes 36 votes Priya_das commented May 18, 2015 reply Follow Share I know Nth fibonacci no ,we can find in O(2^n)but how we are getting GCD in O(log n) ???@arjun sir plz help 1 votes 1 votes Arjun commented May 18, 2015 reply Follow Share @Priya No. We are not finding the nth Fibonacci number. We need 'n' recursive calls to find the GCD of nth and n+1th Fibonacci numbers. And nth Fibonacci is of the order of 2n. Now, we have n - so it will be of the order of (log n)th Fibonacci number and hence require log n recursive calls. 36 votes 36 votes MiNiPanda commented Oct 6, 2018 reply Follow Share F0=0, F1=1, F2=1, F3=2, F4=3 .... I have one doubt : gcd(Fn,Fn−1)=gcd(Fn−1,Fn−2)=⋯=gcd(F1,F0)=1 Did you mean gcd(Fn,Fn−1) calls gcd(Fn−1,Fn−2) calls⋯gcd(F1,F0)=1? If so then i don't think any pair of (Fn,Fn−1) where n>2 will call upto (1,0). It will stop at F3,F2 Eg: gcd(8,5) calls gcd(5,3) calls gcd(3,2) calls gcd(2,1) which is equal to 1 gcd(2,1) : n=2 , m=1 n%m==0 so function returns m and does not call gcd(1,0). Though this doesn't matter here but still I wanted to clarify. This example would never have crossed my mind. Thanks a lot :) 5 votes 5 votes Ashutosh_k commented Apr 12, 2019 reply Follow Share @arjun sir, how do we conclude the last line from the first paragraph of the explanation ? Please elaborate on how we got the number of recursive calls = O(log n) when we want to find gcd(n,m). 0 votes 0 votes Manu Shaurya commented Jun 17, 2019 reply Follow Share I didn't understand how golden ratio is contributing to the final answer, also how did we come to the conclusion that it is $\Theta (logn)$ 2 votes 2 votes Sambhrant Maurya commented Jul 19, 2019 reply Follow Share nth Fibonacci number is 1.618^n, where 1.618 is the Golden ratio. Not getting this. Can you show how? 0 votes 0 votes Mayank0343 commented Aug 1, 2019 reply Follow Share Are we approximating $1.618^n$ to $2^n$ here? I understood from some online search that nth Fibonacci number is at most $2^n$ 0 votes 0 votes register_user_19 commented Oct 29, 2019 reply Follow Share Mayank0343 no both are different. 1). here time complexity of this algorithm is total number of function call made. And total number of funtion call is maximum when both n , m are consecutive fibonacci number. 2). $F_{k}$ = $\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{k} - (\frac{1-\sqrt{5}}{2})^{k})$ so here $\frac{1+\sqrt{5}}{2}$ is 1.68107 and $\frac{1-\sqrt{5}}{2}$ is -0.61807 (if want to see the prove seach on google, in short finding $F_{k}$ required O(1.618^n) ) 1 votes 1 votes `JEET commented Oct 29, 2019 reply Follow Share Can you please refer the source for this? 0 votes 0 votes 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.