6.8k views
| 6.8k views

Its 2.9 on average; the question asked average number of comparisons on binary search; so as per algo first the middle, then since it is sorted while computing for the middle and equating to it at the same time it is determined which way to go further left or right;

1 2 3 4 5 6 7 8 9 10
For 5: 1
For 2,8 : on second comaprison, i.e., 2
And similarly
For 1,3,6,9: 3
And for 4,7,10: 4

compute it: $$\frac{1 \times 1 + 2 \times 2 + 4 \times 3 + 3 \times 4}{10} = 2.9$$
by (279 points)
edited
Array is [1,2,3,4,5,6,7,8,9,10].

Average number of comparisons depend on how likely each element is to be searched. Suppose each element is equally likely to be searched i.e. every element has 1/10 prob of being searched.

Now searching 5 takes only 1 comparison (it will be found in first trial only).

Then searching 2 or 8 takes 3 comparisons (1 for equality with 5, which was failed, then 1 for less than or greater than, then 1 for equality with 2 or 8).

Then searching 1 or 3 or 6 or 9 takes 5 comparisons (again 1 for less than or greater than, and 1 for equality)

Finally, searching 4 or 7 or 10 takes 7 comparisons.

So average number of comparisons = $\frac{1+2*3+4*5+3*7}{10} = 4.8$.
by Boss (11.2k points)
+2

1 for equality with 5, which was failed, then 1 for less than or greater than

A comparison operation b/w two quantities is always supposed to give you all the necessary information.

For example, comparing $A$ and $B$ will tell you whether $A=B$, or $A>B$ or $A<B$ with just one comparison.

The reason for that is simple. Comparing two integers in your program is an $O(1)$ operation. However, comparing two entities (the elements of your array) need not be an $O(1)$ operation. Let's imagine that you were trying to sort an array of chess players. In this case, you might not have an absolute score for each individual player. To compare two players, you make them play 10 games of chess and decide the result of the comparison based on how many games each won or tied. This is an extremely expensive calculation, and you wouldn't wanna do it multiple times.

Hence, you define a comparison operator that returns all the information in 1 single go.

+1

Lets go through steps in algorithm...

if we have to search 2 then

while( low<=high)

{

mid=(low+high)/2

if(a[mid]==2) return a[mid] ........1st comparision

else if(a[mid]>a[i]) high=mid-1;......2nd comparision

else low=mid+1

}

when the number is not found at mid it does 2 comparison in the loop...

and then third comparison for checking a[i]==a[mid]

so 4.8 should be correct..

moreover in the soln with 2.9 it should be divided by 10

and the analogy you defined for chess player score...if there is comparison explicitly made then it should be accounted...

for eg. if we compare two strings we don't say  that string comparison is O(1) rather its O(n) where n is length of string...

pls correct me if I am wrong..:)

+4

The algorithm given in the CLRS book abuses the notation, but doesn't misuse it.

Here's what the correct algorithm would look like (what CLRS implies)

/** returns 1 if a > b
-1 if b > a
0 if a = b     */
int compare(int a, int b);

// Algorithm:

while(low<=high){  // this comparison doesn't count

mid=(low+high)/2

int comp_result = compare(a[mid], a[i]);// THIS IS THE ONLY ONE THAT COUNTS

if(comp_result == 0)      return a[mid]     // this comparison doesn't count
else if(comp_result == 1) high=mid-1;       // this comparison doesn't count
else low=mid+1 //this is a comparison as well. this comparison doesn't count
}
+1

pls give any reference to what you said...

AFAIK the thing you are mentioning is actually at the level where abstraction comes into picture..

Here you are not mentioning how does the compare function returns the required result in just one comparison..

So at abstract level one cannot comment about your comparison and counts it as a single primitive operation..

for eg. the multiplication algorithm at the processor level may be implemented in O(n^2) or O(n*logn) or O(n)...but since we do not know how it is implemented we, whenever use multiplication count it as 1 primitive operation...

but if you implement the multiplication of number yourself u can  exactly count in how many steps, comparison or whatsoever things it does the calculation..

I agree with the rest of things.. even i counted only the comparisons where array elements are compared..:)

0

the multiplication algorithm at the processor level may be implemented in O(n^2) or O(n*logn) or O(n)...but since we do not know how it is implemented we, whenever use multiplication count it as 1 primitive operation

Yes, that can happen. And in that case, the time complexity of the single comparison operation would be $O(n^2)$ or whatever.

Notice the difference b/w finding the number of comparisons made by an algorithm, the time complexity of the algorithm, the number of swaps made by an algorithm and so on..

In the example you gave, the algorithm would make say $\Theta(\log n)$ comparisons, and each comparison would take say $\Theta(n^2)$ time, making the total time complexity of the algorithm to be $\Theta(n^2 \log n)$. The time complexity is more doesn't mean the number of comparisons are more as well.

0
No i didn't wanted to say that time complexity necessarily has to do anything with number of comparison ....

I am saying that one cannot say that your compare function actually makes single comparison to return the value 1,0 or -1 until you clearly specify what your function does...

for eg. If I don't mention about the merge procedure in merge sort algorithm u cannot comment about how many comparisons I actually made in the algorithm...

PS: I want to say...please mention your compare function that returns -1 0 or 1 value in just one comparison...:)
+1
+1
Its ambiguous. In GATE they will say which one they meant. Or else choice will help.

given that 10 consecutive integers starting from 1 so the numbers are 1 2 3 4 5 6 7 8 9 10

for binary search we first compare with the mid value( low=0,high=9 (0+9)/2=4) )

if mid value is the required value then we require only one comparison(for 5:One comparison)

for 1 and 6 we require 2 comparisons (one comparison is for 5 another is for 1 or 6)

for 2 and 7 we require 3 comparisons (two from above comparison another is for 2 or 7)

for 3 and 8 we require 4 comparisons(three from above comparison another is for 3 or 8)

for 4 and 9 we require 5 comparisons(three from above comparison another is for 4 or 9)

therfore average is =(1*1+2*2+3*2+4*2+5*2)/10=2.9

by (17 points)

1