The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+22 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

asked in Algorithms by Veteran (52.1k points)
edited by | 3.3k views

2 Answers

+28 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.9k points)
edited by

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.

na na... return 1... is 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
: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.
ok..yes u right sir..

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

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

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

we discussed here lot

still not satisfactory result.

@arjun sir, good clarification sir
Shouldn't it be for 17 .. we check for 2,3,4 ? Why is it written , for 17 check for ... 2,3,5 ?
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 Junior (677 points)
If we check for N= 2 the n%2== 0 it will be printed that not prime..

But I think 2 is prime...
It is not checking for 2 right?

Related questions

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
49,811 questions
54,533 answers
75,580 users