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.4k 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 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.
12 votes 12 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.