Skip to content
GATETECH
Official PYQ · 2004Q42Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2004 Q42 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

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

x = m;
y = 1;
While (x-y > ϵ)
{
    x = (x+y)/2;
    y = m/x;
}
print(x);
Choose one option
View worked solution

Answer: C

To understand what the algorithm approximates, let us trace the variables xx and yy through the loop iterations.

1. Initial State:
Initially, x=mx = m and y=1y = 1. Note that their product is ximesy=mimes1=mx imes y = m imes 1 = m.

2. Loop Invariant:
Inside the while loop, the variables are updated as follows:

  • xnew=x+y2x_{\text{new}} = \frac{x + y}{2}   (Arithmetic Mean of xx and yy)
  • ynew=mxnewy_{\text{new}} = \frac{m}{x_{\text{new}}}
After these updates, the product of the new values is: xnew×ynew=xnew×mxnew=mx_{\text{new}} \times y_{\text{new}} = x_{\text{new}} \times \frac{m}{x_{\text{new}}} = m Thus, the relation x⋅y=mx \cdot y = m is maintained as a loop invariant at the end of every iteration.

3. Termination Condition:
The loop terminates when the difference between xx and yy becomes extremely small, i.e., x−y≤ϵx - y \le \epsilon.
At this point, we have: x≈yx \approx y Substituting this into our invariant x⋅y=mx \cdot y = m gives: x2≈m  ⟹  x≈m=m12x^2 \approx m \implies x \approx \sqrt{m} = m^{\frac{1}{2}}

This is the classic Babylonian method (a special case of the Newton-Raphson method) for computing the square root of a number. Therefore, the algorithm approximates m12m^{\frac{1}{2}}.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions