How to prove/make sure that the answer to this question will be m^1/2 My friend/colleague who just completed her Bachelors degree in Computer Science is now preparing for a Graduate Aptitute Test. Today she asked me about a question related to Complexity Analyis (Big-O Notation specifically) which I easily solved, and then came another question at which I got stuck. Question Statement was:


What does the following algorithm approximate?

x = m;
y = 1;
while (x - y > e)
{
   x = (x + y)/2;
   y = m/x;
}
print(x);


(Assume m > 1, e > 0).
Options:
(A) log m
  (B) $m^2$
  (C) m^1/2
  (D) m^1/3


Initially I assumed upon looking at the code that the answer would be (C), she also came up with that answer as well (she didn't actually solve it), to my surprise it was actually correct as I cross-checked the answer here. When I looked for the explanation, it said:

The given code is implementation of Babylonian method for square root

Easy, right? But since there wasn't anything like Number Theory in our syllabus (although there were Engineering Mathematics, Discrete Mathematics and Numerical Methods for Engineers) I did not know anything  about this method, meaning that I had to solve it by myself (which I thought would be pretty easy since these type of questions have to be solved in one minute, if you want to attempt all the questions). So I took a paper and a pen (second time) before telling her that I'll get it solved in the morning and started solving it, trying to keep it simple but eventually made it complex (images attached).


The only thing that I could deduce was that the complexity of the code was O(logM) and X halves (approximately) in each iteration and Y doubles (approximately) in each iteration. That wasn't the required answer, so I assumed that I was missing something, so I looked up the Babylonian Square Root Algorithm and found out that the complexity was O(logN) and the code provided above was a little messed up since
while (x - y > e)

which was actually meant to be
while (x - y)

The e was just added to make it more complex, also it would make the problem to solve by trial and error if someone assumed e to be a large value (although it was an easy job if someone assumed e=1 and m=100).
I figured that maybe if I write a code to generate some statistics, then I might be able to figure something out, so I wrote this:
#include<iostream>
int main(int argc, char** argv)
{
    float x,y=1,m,e;
    std::cin>>m>>e;
    x=m;
    while(x-y>e)
    {
        x=(x+y)/2;
        y=(m/x);
        std::cout<<x<<"\t"<<y<<"\t"<<x-y<<std::endl;
    }
    return 0;
}

Initially, I found out that e was actually a culprit, as providing larger values would affect the answer by not letting it completely finish.
The problem still remained, how to know that the answer would be $m^2$ ? I don't know, I am a loser when it comes to mathematics (and that is why I need help)
Below is some sample data from two inputs, 100000 5 and 100 5

I could see that both X and Y would converge to the square root of M, and E was the evil variable. Now, in brief, assuming the following that:


*

*Candidate doesn't know about Babylonian Square-root method

*Question has to be attempted ideally within 1 minute

*A well prepared candidate can analyze the complexity easily

*Trial and Error method is only a matter of luck with low probability of success

*The answer doesn't need to be accurate, but approximate


How this problem can be solved?
 A: Maybe e is like $\epsilon$ in math and is supposed to suggest a small positive number.  Then the fact that the loop terminates when $x-y \lt e$ should suggest they are almost equal.  Note that this assumes $x \gt y,$ otherwise it also terminates the first time $x \lt y$.  Anyway, this suggests plugging $x=y$ into the equations and it is easy to derive $x=\sqrt m$  
I don't suggest this is at all rigorous and I think it is a terrible question, but this will get you to the answer.  I think I would just run it by hand for some small $x$ like $8$, notice that it seems to be converging to the square root, and quit.  I can tell $\log 8, 8^{1/2},8^{1/3},8^2$ apart easily.
A: Imagine you've got a rectangle of area $m$. You try to find such side length so that it's a square. So you proceed - start with rectangle $1\times m$. Then take their average as one side. The second side should be such that the area remains equal to $m$. That's the idea. 
But, one could discard other options rather quickly. $m^2$ is absurd, $\log m$ should involve repeated division, maybe $m^{1/3}$? But after trying the algorithm for some small number, one gets that it can't be cubic root. 
