CMI2012-A-04

Question

The below question is based on the following program. In the program, we assume that integer division returns only the quotient. For example $7/3$ returns $2$ since $2$ is the quotient and $1$ is the remainder.

mystery(a,b){
        if (b == 0) return a;
        if (a < b) return mystery(b,a);
        if (eo(a,b) == 0){
             return(2*mystery(a/2,b/2));
    }
    if (eo(a,b) == 1){
        return(mystery(a,b/2));
    }
    if (eo(a,b) == 2){
        return(mystery(a/2,b));
    }
    if (eo(a,b) == 3){
        return (mystery((a-b)/2,b));
    }
}
eo(a,b){
if ((a/2)*2 == a and (b/2)*2 == b) return 0; end;
if ((a/2)*2 < a and (b/2)*2 == b) return 1; end;
if ((a/2)*2 == a and (b/2)*2 < b) return 2; end;
return 3;
}

When $a$ and $b$ are $n$ bit positive numbers the number of recursive calls to $\text{mystery}$ on input $a,\: b$ is

• A. $O(n)$
• B. $O(\log \log n)$
• C. $O(\log n)$
• D. $O(n^{\frac{1}{2}})$

Answer 1

O(log n)

Comments

@Kushagra Chatterje please further explain the answer.

---

i think in worst case the reduction done is n/2.so the equation will be T(n)=T(n/2)+c.so o(logn).please correct me if iam wrong.just a beginner