The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.3k 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.5k points)
edited by | 2.3k 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.7k points)
edited by
+3

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.

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

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.
0
@srestha,
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 ...)
Omega(1)
Worst case means - Big-O. ( If a number is prime )
O(sqrt(n)).
0
@vijay

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
0
@srestha see now..
0
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?

0
@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$.
0

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 immediately......so.... ᘯ(1)...itz clear

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

0
return 1 is not inside the for loop.
0
ok...i got it ....here "inner function" means the inner loops ...ryt?
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 ?


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

38,017 questions
45,509 answers
131,694 comments
48,735 users