Official PYQ · 2007Q51Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2007 Q51 — Asymptotic Worst Case Time and Space Complexity

Consider the following C program segment:

int IsPrime (n)
    {
        int i, n;
        for (i=2; i<=sqrt(n);i++)
            if(n%i == 0)
                {printf("Not Prime \n"); return 0;}
        return 1;
    }

Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$ . Which of the following is TRUE?

View worked solution

Answer: B

To find the correct asymptotic bounds for $T(n)$ , the number of times the for loop is executed, we need to analyze the best-case and worst-case scenarios of the algorithm.

1. Worst-Case Analysis (Upper Bound $O$ )

The worst-case occurs when $n$ is a prime number. In this case, the condition n % i == 0 is never satisfied for any $i$ in the range $[2, \sqrt{n}]$ .

The loop variable $i$ runs from $2$ up to $\lfloor\sqrt{n}\rfloor$ .
The number of iterations is approximately $\sqrt{n} - 1$ .
Therefore, the maximum number of iterations is bounded above by $\sqrt{n}$ , which gives:

T(n) = O(\sqrt{n})

2. Best-Case Analysis (Lower Bound $\Omega$ )

The best-case occurs when $n$ is an even number greater than $2$ (e.g., $n = 4, 6, 8, \dots$ ).

In the very first iteration where $i = 2$ , the condition n % 2 == 0 evaluates to true.
The function immediately prints "Not Prime" and returns $0$ .
Thus, the loop executes exactly $1$ time.
Since the loop executes at least a constant number of times for any input $n \ge 2$ , we have:

T(n) = \Omega(1)

Conclusion

Combining both bounds, we get:

T(n) = O(\sqrt{n}) \quad \text{and} \quad T(n) = \Omega(1)

Hence, the correct option is B.

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

Published 10 Oct 2026

Report a correction

Browse this topic

More Asymptotic Worst Case Time and Space Complexity questions

GATE CS 2007 Q51 — Asymptotic Worst Case Time and Space Complexity

1. Worst-Case Analysis (Upper Bound OOO)

2. Best-Case Analysis (Lower Bound Ω\OmegaΩ)

Conclusion

Related questions

1. Worst-Case Analysis (Upper Bound $O$ )

2. Best-Case Analysis (Lower Bound $\Omega$ )