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