If we are using a binary search on a list of size 1024 what is the worst case nu

ID: 3690745 • Letter: I

Question

If we are using a binary search on a list of size 1024 what is the worst case number of operations we will use to find our target?

If we are searching a linked list of items for a specific item that is not in the list, how many comparisons will we use in the worst case? How many comparisons will we use
on average? How many in the best case? Be exact with your answer.

If we are searching a list of items for a specific item we know is in the list, how many comparisons will we use in the worst case? How many comparisons will we use on
average? Be exact with your answer.

Explanation / Answer

Binary Search

As linear search, the worst case for binary search is when the value x is not in the set L as then the algorithm has to perform the maximum possible number of recursive calls, and hence the maximum possible number of operations

Suppose T(n) unit of time required to search the array of n elements. Now, in the 2nd iteration array is halved. so, in the 2nd iteration T(n/2) time is required and so on. hence we get the following recurrence relation.

T(n)= c+T(n/2) c=some const. time required to find middle element.

= c+T(n/2)2

....................

=kc+T(n/2k)

= c logn+T(1) [Let 2k = n. So, k = log n]

therefore, T(n) = O(log n)

Here n= 1024 so 10 operations will be required.

Linked List

Worst Case:

suppose there are n number of records.

For an unsuccessful search the list will be visited till the last record.

therefore T(n) = O(n)

Average case:

The element can be found in any position in the list and the probability is 1/n. Now if the element is found in the first position only one comparison equired,for the second position two comparisons are required and so on. Hence,

f(n) = 1/n+2/n+.......+n/n

=(1+2+.....+n)/n

=n(n+1)/2n

=(n+1)/2

Therefore, T(n) = O(n)