TIFR CSE 2020 | Part B | Question: 7

Question

Consider the following algorithm (Note: For positive integers, $p,q,p/q$ denotes the floor of the rational number $\dfrac{p}{q}$, assume that given $p,q,p/q$ can be computed in one step):

$\textbf{Input:}$ Two positive integers $a,b,a\geq b.$

$\textbf{Output:}$ A positive integers $g.$

while(b>0) {
             x = a – (a/b)*b;
             a = b;
             b = x;
        }

g = a;

Suppose $K$ is an upper bound on $a$. How many iterations does the above algorithm take in the worst case?

• A. $\Theta(\log K)$
• B. $\Theta({K})$
• C. $\Theta({K\log K})$
• D. $\Theta({K^{2}})$
• E. $\Theta({2^{K}})$

Comments

Given algorithm is a variation of classical algorithm to find gcd of 2 numbers which is called Euclidean Algorithm.

Here, we can replace $" a - \lfloor{a/b}\rfloor *b "$ by $ a \%b$

This algorithm terminates atmost $2log_2max(a,b)$ number of iterations. since here $a \geq b$ and $a$ is upper bounded by $K$. So, in worst case, total number of iterations = $O(logK)$ but how to show $\Omega(logK)$ ?

---

the code is not written properly