Vani test series question

Question

https://gateoverflow.in/?qa=blob&qa_blobid=16020532755515515346

Shouldnt the answer be option d? How option c?

Comments

according to me worst best case happens when these two numbers are prime numbers...

and maximum value can be obtained usind gcd(m,n) =O(logn)

.

best case hapeens when they are non prime : consider m=8, n=4

       we have to find min(m,n) then check this value dividing each of two by the min-- .             = O(1). or omega(1)

so D is true.

---

1.Best case can happen when both numbers (30,30) are same or the samllest  (5,30) number is the divisible of both (m,n)? If so then time comp will be bigO(1)/omeg(1)/teta(1).

2.Even if we consider your point of view  in the option c it is not bigO(n) they have given omega(n) which they mean that it cannot be lesser then n. Where n corresponds to the smallest of m,n.

Correct me if I'm wrong.

Answer 1

Option D is correct as 

Best case occurs when m%n==0 or n%m==0 which takes omega(1) time

worst case occurs when two numbers are prime or co-prime which takes logn time ie O(log₂ (min (m,n))) 

Comments

But if you notice in option c it is omega (n) not omega (1).

---

by mistake I wrote option C