What does the following algorithm approximate? (Assume m>1,ϵ>0)
By simply looking at the structure of the loop, we know that if the while loop terminates after going into the loop (I'll assume this for simplicity as it's the interesting case) that $y=\frac{m}{x}$ (last instruction) and that $x-y&lt;\epsilon$ (exit condition). Combining the two gives you $x&lt; \sqrt{m+x\dot\epsilon}$. If you manage to notice that $x\geq y$ at the end of each iteration of the loop, then you also get $x\geq y=\frac{m}{x}$ and therefore $\sqrt{m}\leq x&lt; \sqrt{m+x\dot\epsilon}$.



You could write down the sequence of values taken by $x$ and $y$ mathematically (this is what you would do anyway to prove correctness and termination of the algorithm if you knew what it did/was supposed to do, but it can also help you to determine this!).

Initially, $\begin{cases}x_{0}=m\\ y_{0}=1\end{cases}$.
At the end of the $n^{\text{th}}$ iteration of the while loop: $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$

Now, analysing the two sequences we find that:


$(x_n)$ is decreasing
$(y_n)$ is increasing
$x_0&gt;y_0$


This is enough to say both sequences converge (as they are monotonic and bounded), to say $x$ and $y$. Using $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$ we can say that $x=y$.

So $\forall n&gt;0,x_n\geq x=y\geq y_n$. In particular the algorithm must terminate (as $x_n-y_n$ is non-negative and converges to $0$). From there you can continue like in the first part ('By simply looking at the$\dots$').