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'

?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 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);

- $\log \, m$
- $m^2$
- $m^{\frac{1}{2}}$
- $m^{\frac{1}{3}}$

+34 votes

Best answer

+1

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

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

0

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.

0

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

Reference : http://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity

0

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

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

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

+4 votes

This is an implementation of Babylonian method for square root - http://www.geeksforgeeks.org/square-root-of-a-perfect-square/

its time complexity is - log(log(n/e)) -https://stackoverflow.com/questions/12309432/time-complexity-for-babylonian-method

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,879 questions

47,536 answers

146,083 comments

62,300 users