retagged by
14,670 views
25 votes
25 votes

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

  1. $\log n$
  2. $\frac{n}{2}$
  3. $\log_2 {n} - 1$
  4. $n$
retagged by

6 Answers

Best answer
29 votes
29 votes

A & C are not correct as we can not do binary search efficiently {it takes O(n)} in Linked list.

B seems like average case, be we are asked for worst case.

Worst case is we do not find the element in list. We might end up searching entire list & comparing with each element. So, answer -> (D). $n$

edited by
9 votes
9 votes

 Binary search algorithm is based on the logic of reducing your input size by half in every step until your search succeeds or input  gets exhausted. Important point here is "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

8 votes
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).
4 votes
4 votes

There are n elements so Log2n 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 

Answer:

Related questions

20 votes
20 votes
1 answer
1
Kathleen asked Sep 15, 2014
2,501 views
Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$.
39 votes
39 votes
8 answers
2
Kathleen asked Sep 15, 2014
17,639 views
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
32 votes
32 votes
5 answers
3
Kathleen asked Sep 15, 2014
13,671 views
In the absolute addressing mode:the operand is inside the instructionthe address of the operand in inside the instructionthe register containing the address of the operan...
21 votes
21 votes
1 answer
4
Kathleen asked Sep 15, 2014
8,013 views
The optimal page replacement algorithm will select the page thatHas not been used for the longest time in the pastWill not be used for the longest time in the futureHas b...