14,113 views
33 votes
33 votes

What does the following algorithm approximate? (Assume $m > 1, \epsilon >0$).

x = m;
y = 1;
While (x-y > ϵ)
{
    x = (x+y)/2;
    y = m/x;
}
print(x);
  1. $\log \, m$
  2. $m^2$
  3. $m^{\frac{1}{2}}$
  4. $m^{\frac{1}{3}}$

6 Answers

Best answer
76 votes
76 votes
By putting $y = m/x$ into $x = ( x + y )/2$
$\quad x= ( x + m/x ) /2$

$\implies 2x^2= x^2 + m$
$\implies x = m^{1/2}$

We can also check by putting $2$ or $3$ different values also.

Correct Answer: $C$
edited by
28 votes
28 votes

First of all this question is about approximation of value. So we can do 1 step more or less. That will not affect the answer.

Answer given by @gate_asp is somehow appropriate, but it doesn't answer some questions which are mentioned in comments. 

So here is my ans. 

loop will terminate in (Log Log n) iterations. at that time if x is a perfect square number then it x = y = $m^{1/2}$

otherwise it will terminate with condition y > x.

21 votes
21 votes

take m=8 and trace the Algorithm and verify the options A.3  B.64  C.2$\sqrt{2}$=2.82  D.3

Imp Note:-> we cant take variable type as int (cz it is an algorithm as specified in question) if U do so we end up with incorrect result

Now Trace the algorithm

Initially m=8 , $\epsilon$=1 , x=8 , y=1

Iteration # x y while(x - y >1)
1 8 1     True
2 4.5 1.78     True
3 3.14 2.55     True
4 2.85 2.8      False

So it match with Option C .

Answer:

Related questions

47 votes
47 votes
7 answers
2
Kathleen asked Sep 18, 2014
17,289 views
The recurrence equation$ T(1) = 1$$T(n) = 2T(n-1) + n, n \geq 2$evaluates to$2^{n+1} - n - 2$$2^n - n$$2^{n+1} - 2n - 2$$2^n + n $
31 votes
31 votes
6 answers
3
Kathleen asked Sep 18, 2014
19,267 views
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...