edited by
14,453 views
38 votes
38 votes

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?
 

  1. $T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(\sqrt{n})$

  2. $T(n) = O(\sqrt{n}) \: \text{ and } T(n) = \Omega(1)$

  3. $T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$

  4. None of the above

edited by

5 Answers

Best answer
51 votes
51 votes

Answer is option B.

Worst Case : $T(n) = \mathcal{O}(\sqrt{n})$

Best Case : When $n$ is an even number body of $for$ loop is executed only $1$ time (due to "$return \ 0$" inside if) which is irrespective of $n$. $\therefore T(n) = \Omega(1)$

edited by
8 votes
8 votes

"return 0" acts as an exit condition. Basically, "return 0" means "success" — hence, no need to proceed further.

int IsPrime (n)
    {
        int i, n; 
    /* Take n = 100 */
        for (i=2; i<=sqrt(n);i++) 
    /* Would run O(√100) times, normally. */
            if(n%i == 0) 
    /* True, so enter "if". */
                {printf("Not Prime \n"); return 0;} 
    /* return 0 means, "Success!
    This number is successfully determined to be non-prime,
    hence no need to go on." So, we exit for-loop */
        return 1;
    }

Hence, in the best case, we'll encounter "return 0" at the first iteration, so Ω(1).

In the worst case, it'll go from i = 2, to i = √n — never encountering "return 0" — means O(√n) times.

So, Option B.

 


 

If the code was like this:-

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

Then, there's no early exit condition (return 0). Then, Option A would be the answer, because the only way for-loop would be broken out of, is to iterate completely.

3 votes
3 votes

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

int i, n;

 

Input n was sent to the function, but the function creates its own auto variable n which takes garbage value. The number of times the loop runs does not depend on the input n sent.

D. None of these

0 votes
0 votes

Option B

The RR will be 

T(n)=T(sqrt(n))+C.

TC will be O(loglog(n))

Now,

Loglog(n) <= C1.sqrt(n) satisfies. (C1 is some constant)

so, loglog(n)=O(sqrt(n))

Loglog(n)>=C2.1 satisfy. (C2 is some constant)

so, loglog(n)= Omega(1)

Answer:

Related questions

64 votes
64 votes
15 answers
1
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...
50 votes
50 votes
8 answers
2
Kathleen asked Sep 21, 2014
31,722 views
What is the $\text{time complexity}$ of the following recursive function?int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); ...
64 votes
64 votes
8 answers
3
Kathleen asked Sep 21, 2014
26,380 views
In the following C function, let $n \geq m$.int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); }How many recursive calls are made by this function?$\Theta(\...