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 (59.4k points)
edited by | 2.2k views

1 Answer

+24 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.6k points)
edited by

I think here explanation for best case in not correct. Best or worst case should be irrespective of n. But think if n is divisible by 2 or 3 or 5 ...  
And  Nithish Ganeshbabu  , for worst case , take any prime number .. you will need to execute for loop for $\sqrt{n}$ times.

As it is only depend on for loop, in that case A) could be answer

it could be O(1), as in some cases best case also takes O(1).

Like insertion of a node at the front of Linked List.
Yes, for insertion of a node at the front of LL is - O(1) but how O(1) for checking prime number?
Best case means- Omega . ( If a number is div. by some small number like -2 or 3 or 5 ...)
Worst case means - Big-O. ( If a number is prime )

think like this

if we know the prime numbers , in between sqrt(n)

then only checking those numbers we can get it.

like for 17

we can check only by 2,3,5

So, some constant number of checking.

will give O(1) complexity
@srestha see now..
for (i=2; i<=sqrt(n);i++)
            if(n%i == 0)
                {printf("Not Prime \n"); return 0;}

ok, if this is the code then A) could be answer.

But here only one time for could go inside if. As bracket of for not there , will it not executed one time for every possible input?

Then in worst case also executed 1 time, isn't it?

@srestha we cannot give $n=1$ and say in best case it is $O(1)$ or $\Omega(1)$ because $\Omega(n)$ is also true here. The reason for "best case" previously given in answer was wrong. $O(1)$ means it is INDEPENDENT of $n$.

arjun sir plz help....

"return in an inner function (not main) will terminate immediately the execution of the specific function returning the given result to the calling function."

return 0 will terminate ᘯ(1)...itz clear

return 1 will .....???? not terminate immediately ....??? why...plz explain

return 1 is not inside the for loop.
ok...i got it "inner function" means the inner loops ...ryt?

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 ?

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

36,194 questions
43,647 answers
42,930 users