The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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;
  1. $\log \, m$
  2. $m^2$
  3. $m^{\frac{1}{2}}$
  4. $m^{\frac{1}{3}}$
asked in Algorithms by Veteran (69k points) | 1.7k views
In question it is mentioned e>0

This condition is very ambiguous as assuming e much greater than x will result in x itself ( loop condition fails).

I understand , in exam most appropiate option is to be chosen

But what if, another option given as 'x'


4 Answers

+28 votes
Best answer
by putting $y = m/x$ into $x = ( x + y )/2$

$x= ( x + m/x ) /2$

$=> 2x^2= x^2 + m$
$=> x = m^1/2$

or we can check by putting 2-3 different  values also.
answered by Junior (757 points)
edited by
The input value of X in expression 1 is different from th einput value of X in expression 2.

How can we substitute expression 2 in 1? we need to do vice varsa right? though both gives same answer

Yes, the ans draw is seeming correct.

But i think @exam we cant rely and put ans like this.

Reason1->>In Ans they have not considered condition  While (x-y > ϵ)

Reason2->>How can u put step2 in step1 without executing step1 cz Program runs sequentially.

can someone tell the time complexity of this code?? is itO( log log n)???

Yes, time complexity is O(loglogn) as the subproblem size is getting shrinked by √n 

Reference :

@Ayush Upadhyaya 

>>>Yes, time complexity is O(loglogn) as the subproblem size is getting shrinked by √n 

I think this statement is not correct. This is a numerical method of computing square root.  

Output will be different for different values of $\epsilon$.
I think none of the answers is correct here ... assume m = 4 and epsilon = 8

(4-1=3) is not greater than 8

so print x which is 4

None of them matches right . ?
+5 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 .

answered by Veteran (23.4k points)

In 3rd iterarion How are you getting 3.14 ?
For me the loop stops at rd iteration and output x as 2.75  .  But your trace has got 4 iterations .Moreover Your option D is 3 . It should be 2 .

Tough the answer does not change much

+3 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.


answered by (119 points)
+3 votes

This is an implementation of Babylonian method for square root -

its time complexity is - log(log(n/e)) -

answered by (145 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
38,664 users