The GATE Grind

GATE 2007 CS – Question 51

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

Let T(n) count loop executions in this C code. Which is TRUE?

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;
}
  1. $T=O(\sqrt n)$ and $T=\Omega(\sqrt n)$
  2. $T=O(\sqrt n)$ and $T=\Omega(1)$
  3. $T=O(n)$ and $T=\Omega(\sqrt n)$
  4. None of these.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $T=O(\sqrt n)$ and $T=\Omega(1)$

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Asymptotic Analysis and Time/Space Complexity questions

All Asymptotic Analysis and Time/Space Complexity questions →