15 votes

In the worst case, the number of comparisons needed to search a single linked list of length $n$ for a given element is

- $\log n$
- $\frac{n}{2}$
- $\log_2 {n} - 1$
- $n$

24 votes

Best answer

8 votes

Since, It is not possible to do a Binary search in Linked List, the Only solution is linear search so its O(n).

6 votes

**"the step to reduce input size should take constant time". **In case of an array, it's always a simple comparison based on array indexes that takes O(1) time.

But in case of Linked list you don't have indexes to access items. To perform any operation on a list item, you first have to reach it by traversing all items before it. So to divide list by half you first have to reach middle of the list then perform a comparison. Getting to middle of list takes O(n/2)[you have to traverse half of the list items] and comparison takes O(1).

Total = O(n/2) + O(1) = O(n/2)

So the input reduction step does not take constant time. It depends on list size. hence violates the essential requirement of Binary search.

thts why d is the answer only in worst case

4 votes

There are n elements so Log_{2}n is not the case in single linked list because binary search not possible so option A and C is wrong

In worst case there are n comparisons so option D is right