+1 vote
66 views

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 $mystery$ on input $a,\: b$ is

1. $O(n)$
2. $O(log log n)$
3. $O(log n) 4.$O(n^{\frac{1}{2})\$
| 66 views

## 1 Answer

0 votes
O(log n)
by Loyal (9.6k points)

+1 vote
1 answer
1
+3 votes
1 answer
2
+1 vote
1 answer
3
+4 votes
1 answer
4
+10 votes
4 answers
5
+1 vote
0 answers
6
+1 vote
1 answer
7