GATE CS 1991 Q03-viii — Asymptotic Worst Case Time and Space Complexity

To find what the function returns for a positive integer $N$, let us analyze the loop condition and termination behavior.

The loop starts with $i = 0$ and increments $i$ by $1$ in each iteration as long as:

The loop terminates as soon as this condition becomes false, which means it stops at the smallest non-negative integer $i$ such that:

Taking the square root on both sides (since $i \ge 0$ and $N > 0$):

The smallest integer $i$ that is greater than or equal to $\sqrt{N}$ is, by definition, the ceiling of $\sqrt{N}$:

Dry Run Examples:

• Case 1: $N = 9$ (a perfect square)
  • $i = 0 \implies 0^2 < 9$ (True) $\implies i = 1$
  • $i = 1 \implies 1^2 < 9$ (True) $\implies i = 2$
  • $i = 2 \implies 2^2 < 9$ (True) $\implies i = 3$
  • $i = 3 \implies 3^2 < 9$ (False) $\implies$ Loop terminates.
  • Returns $3$, which is $\lceil \sqrt{9} \rceil = 3$.
• Case 2: $N = 8$ (not a perfect square)
  • $i = 0 \implies 0^2 < 8$ (True) $\implies i = 1$
  • $i = 1 \implies 1^2 < 8$ (True) $\implies i = 2$
  • $i = 2 \implies 2^2 < 8$ (True) $\implies i = 3$
  • $i = 3 \implies 3^2 < 8$ (False) $\implies$ Loop terminates.
  • Returns $3$, which is $\lceil \sqrt{8} \rceil = \lceil 2.828 \rceil = 3$.

Thus, the function returns $\lceil \sqrt{N} \rceil$.