The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.5k views

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

asked in Algorithms by Veteran (59.6k points)
edited by | 2.5k views

2 Answers

+25 votes
Best answer

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)$

answered by Boss (19.7k points)
edited by
0
@Tauhin

Scope of for() loop is entirely if () condition, which returns 0.

and it's else portion returning 1.

So, while returning 1 , it is going inside for loop again.

and when returning 0, then it breaks for loop and terminates.

rt?
0
na na... return 1... is normal...execution..as compiler executes step by step....u cannot consider it "else " part... bcoz if u consider it else...then it b inside for loop....i m still not very clear
+1
:O "return 1" is not part of "if" or "else" or even the for loop. Hence it does not affect the answer here. There is no implicit "else" in C or any language I know.
0
ok..yes u right sir..
0

@Tauhin_Gangwar , @arjun sir , @srestha
:O Do the return 1 or 0 statement inside a loop make so much difference in execution of the code ? If so could you pls explain little bit detail How it is working ?

(  What i knew is these numbers are used for exception handling purpose )

+2
Take n= any even number

any loop or condition only evaluated one time

And returning 0 , means go outside all loops

So,$\Omega (1)$

it is also true for $\Omega (n)$

i.e. why ans is $\Omega (1)$
0

Actually question here difference between return 1, return 0, return -1.

we discussed here lot https://gateoverflow.in/95656/programming

still not satisfactory result.

0
@arjun sir, good clarification sir
0
Shouldn't it be for 17 .. we check for 2,3,4 ? Why is it written , for 17 check for ... 2,3,5 ?
0
Can you explain both the cases by taking some value of n....
0 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

answered by (167 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,856 questions
47,522 answers
145,899 comments
62,280 users