The Gateway to Computer Science Excellence
+36 votes
9.4k 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:

  1. $\lceil \log_2n \rceil +1$

  2. $n$

  3. $\lceil \log_2n \rceil$

  4. $\lfloor \log_2n \rfloor +1$

in Algorithms by Veteran (425k points)
edited by | 9.4k views
0
d is correct
0
It is D)..
0
flor|logn|+2 is valid for takes the value of n either even or odd
+1
i guess if we determine number of iterations than comparisons here it would be an useful analogy
0
This question needs some correction.
+6

correct answer should be floor(log n)+2

0
Can you explain
+2
When  I am taking n=20 here.No of comparisons performed are 6.

For j=1,2,4,8,16,32 While loop is run

But ceil(20) + 1 = 5.

What am I missing ?
0

@sushmita correct answer will be D . 

and if they ask total no of comparison then answer will be $\left \lfloor log n \right \rfloor$+2

+1

@Gurdeep Saini why (A) is not the correct option?

0

@chauhansunil20th take n=3 then you will get 3 from option a and 2 from option d

+1

if $n=3$, then following are the comparisons:
$1<=3$
$2<=3$
$4<=3$

what is the issue there are 3 comparisons made by the program @Gurdeep Saini?

 

0
total comparisons is 3

but number of comparisons made in the execution of the loop =2
0
Just 25 days are left and you're playing comment - comment :/
$1<=3 $
$2<=3 $
$4<=3$

Don't you see these 3 comparisons, there are 2 successful and 1 unsuccessful comparisons. total comparisons are 3, and it is not mentioned in the question that we need to count only successful comparisons.
+1
do you know what is the execution of loop ?

IF entry condition fail the this will not be count in the execution of loop
0

@Gurdeep Saini If it had asked for the no of comparisons then the answer would have been A ?? As its asking for only no of time's the loop gets executed, so we are not considering the last comparison as then the loop condition fails. (Am I right??)

0

@Rishav_Bhatt no 

then answer will be ⌊log n⌋+2.

13 Answers

+54 votes
Best answer
$$\begin{array}{|c|l|c|} \hline \text{n} & \text {No. of comparisons} & \text{$\lfloor \log_2 n\rfloor + 1$}\\\hline \text{1} &  \text{$2 \;(j = 1,2)$} & \text{1}\\\hline \text{2} & \text{$3\; (j = 1,2,4)$} & \text{2} \\\hline \text{3} & \text{$3\; (j = 1,2,4)$} & \text{2} \\\hline \text{4} & \text{$4 \;(j = 1,2,4,8)$} & \text{3} \\\hline  \text{5} & \text{$4\; (j = 1,2,4,8)$} & \text{3} \\\hline \end{array}$$
We have to count those comparisons which happens during the execution of the loop and so the exit comparison must also be a part. So, the correct answer should be $\lfloor \log_2 n \rfloor + 2.$

Since this is not in the choices we can assume that the question setter excluded the exit comparison and so the answer should be  $\lfloor \log_2 n \rfloor + 1.$

Option D.
by Boss (13.5k points)
selected by
+1
When $n=5$, there are  $4$ comparisons $(j=1,2,4,8)$
+3

for n = 5, total comparisons are 4 (not 3) --> j = 1, 2, 4 & 8 (last comparison turns out to be false) 

so, total comparisons are 4

And loop is executed 3 times.

+13
  n    Total No. Of Comparisons #Comparisons that result in execution of while loop  (A) Ceil(lgn)+1  (D) Floor(lgn)+1 
1 j=1,2 (2) 1 0+1=1 0+1=1
2 j=1,2,4(3) 2 1+1=2 1+1=2
3 j=1,2,4(3) 2 2+1=3 1+1=2
4 j=1,2,4,8(4) 3 2+1=3 2+1=3
5 j=1,2,4,8(4) 3 3+1=4 2+1=3
6 j=1,2,4,8(4) 3 3+1=4 2+1=3
7 j=1,2,4,8(4) 3 3+1=4 2+1=3

Now, if we consider #Comparisons that result in execution of while loop(excluding the last one that results in loop condition being false) , Answer should be (D).

If we consider Total #Comparisons answer should be : Floor(lgn)+2

0

how you have made comparisons here..

n=? what is the value of n here

j==????

0
For  n=100 we have 7 comparisons including loop break....if we take ceil of logn base 2 +1 we will get exact answer

So why not option A is answer..
0
there are 8 comparisons for n = 100 including loop break.

1. current value of j =1; compare; j =2 is the new value of j

2. current value of j =2; compare; j =4 is the new value of j

3. current value of  j =4; compare; j =8 is the new value of j

4. current value of  j =8; compare; j =16 is the new value of j

5. current value of  j =16; compare j =32 is the new value of j

6. current value of  j =32 compare j =64 is the new value of j

7. current value of  j =64 compare j =128 is the new value of j

8. current value of  j =128 compare fails.
+17 votes
Assuming that "comparisons made in the execution of the loop" means that comparison made while loop is executing, last comparison is not counted.

Say we have j = 7.

Then successful comparisons are 1,2,4. (We get out in next comparison.) So 3 comparisons

Then

A) Incorrect as We get 21 !=3.

B) Incorrect, this is 8.

C) Correct

D) Correct

C & D both gave 3

In C & D for tie breaking, we can take j = 8. No of comparisons (Successful) -> 1,2,4,8.(We get out of loop in 16)

C) 3 != 4. Incorrect

D) 4 Correct

 

Answer -> D
by Boss (41.6k points)
+9

why you are considering successful comparisons ???what about the last comparison ? when n=20 , 5 successful & 1 unsuccessful comparison are there.!

+6

Because the unsuccesful comparison does not leads to the execution of the loop and thats why it is not taken into consideration
 

+1
That means question is incorrect or incomplete.
0

Akash Kanase  why we not consider last comparisons if we take last one answer will be A part

0
ambiguous ques
0
@Sarvottam patel , your answer saved my day.
0

@Akash Kanase sir , is the statement "made in the execution of the loop" the catch here ? 

+14 votes
n Number of Comparisons   
1 2(j=1,2)  
2 3(j=1,2,4)  
3 3(j=1,2,4)  
4 4(j=1,2,4,8)  
5 4(j=1,2,4,8)  

Answer should be None of these here.I think Answer should be $\lfloor \log_2n \rfloor +2$ .

by Boss (41k points)
edited by
0

@ Arjun  Sir, Please check this solution

0
leen sharma I am agree with you
0
option A is correct check it
+7 votes

All the options fail for n = 2, 4, 8, 16... 

The correct answer to this is -  ⌊log2n⌋ + 2

by Active (3.4k points)
+6 votes

Answer D). Log2n + 1

by Veteran (50.7k points)
+1
@Kapil... Out of given four options option D seems best ...

But, as we are not told to count only successful comparisons, here ans should be |_logn_| + 2 right ??

or ceil[logn] + 1... right ??
0
for successfull comparisons,

take n = 9

1,2,4,8 are only successful, so , it should be C).
0
now take n=8
0
then, also D.

why logn + 2?
0

for successfull comparisons, 

take n = 9

1,2,4,8 are only successful, so , it should be C).

In this case , I thought you got option C as ans if it is asking for successfull comparisons. So I told you to check it for n=8, and it does not satisfy.

But in my first comment, i said that if it is asking for only successfull comparisons then option D is okay but it is not mentioned in the question right.

So here exact ans should be |_log n _| + 2 which is clearly explained by @vikrant sir in below answer.

0
ambigous answer
+6 votes
Answer is a)

say n=4
According to answer d no of comparisons will be 3
but actually there will be 4 comparison
1<=4
2<=4
4<=4
and final comparison will be 8<=4 which will give false ,So total no of comparisons are 4 So d cant be true

Moreover say for 7 node no of comparisons will be
1<=7
2<=7
4<=7
8<=7 i.e also 4
so answer is ceil (logn)+1 i.e option a
by
+4 votes

It should be ⌊logn⌋+2

log2n+1

log2n+1

by Active (2.3k points)
edited by
+4 votes

We have to find the number of comparisons made in the execution of the loop. So, counting the no. of comparisons for which the loop executes. With this fact lets observe what happens to the value of j at each iteration.


Iteration No. 'i'   Value of j at ith iteration
1 1
2 2
3 4
4 8
5 16
... ...
k 2k-1

Lets assume that kth iteration is the last successful iteration of the loop  after which the value of j crosses n.Therefore,

2k-1 > n should hold.

k-1 > log2n

k > log2n + 1

k = ⌈log2n⌉  + 1

Option A seems correct.

Correct me if I am wrong!!!

by Active (1.3k points)

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
50,645 questions
56,542 answers
195,693 comments
101,538 users