Multiple choice

Consider the following C code segment:

int Is Prime (n) 
{
int i, n;
for (i = 2; i <= sqrt (n) ; i ++)
 if (n% i == 0) { 
   print f (“ Not Prime  n”);
   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?

  1. T (n) = O($\sqrt n$) and T (n) =$\Omega$($\sqrt n$)
  2. T (n) = O($\sqrt n$) and T (n) = $\Omega$ (1)
  3. T (n) = O(n) and T (n) = $\Omega$ ($\sqrt n$)

  4. None of the above
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

Keep practicing — related questions