Question

Consider the following C code segment:

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

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

Accepted Answer

The correct answer is (B) T(n) = O(√n) and T(n) = Ω(1). The loop never runs more than about √n times (upper bound O(√n), reached when n is prime and every i must be tried). But it can also exit after just 1 iteration (e.g. n even, i=2 immediately divides), so the best case is Ω(1) — there's no nontrivial universal lower bound. So T(n)=O(√n) and T(n)=Ω(1).

Explanation