The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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$
asked in DS by Veteran (69k points)
retagged by | 1.1k views

5 Answers

+19 votes
Best answer

A & C are not correct as we can not do binary search 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$

answered by Veteran (49.5k points)
edited by
@srestha,how more than n is possible?
yes not possible

more than n is only possible when you apply binary search .

otherwise , by linear method it will take n
worst case is not just element is not found, if searched element is the last element then also N comparision are required...isn't it..?
+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).
answered by Boss (5k points)
But is it asked about complexity? It asked about number of comparison only.
+3 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

answered by Boss (8.7k points)
+3 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 

answered by Veteran (11.2k points)
–1 vote
answered by Junior (855 points)

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

34,170 questions
40,845 answers
39,703 users