search
Log In
15 votes
3.9k views

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$
in DS
retagged by
3.9k views

8 Answers

24 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$


edited by
0
@srestha,how more than n is possible?
0
yes not possible
0
@reena_kandari

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

otherwise , by linear method it will take n
0
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..?
3
SAYING WE CANT DO BINARY SEARCH IS WRONG WE CAN DO BUT IT IS NOT EFFICIENT TO DO BINARY SEARCH IN LINKED LIST IT GIVES ALMOST O(N) TC
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).
0
But is it asked about complexity? It asked about number of comparison only.
0
Binary search is possible on linked list but it is not efficient than linear search so we avoid it and use linear search
0
not impossible but time consuming
6 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

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 

0
In which case searching in single linked list takes n/2- when we get an element in middle of the list.
0 votes

Worst case of searching singly linked list is when given element doesn’t present at all in the singly linked list. Using linear search then required ‘n’ comparisons in worst case. Hence option D is correct.

Note : A & C are not correct as we can not apply binary search in Linked list.

0 votes

Hope this helps :)

–1 vote
O(n)
–1 vote
Answer:

Related questions

14 votes
1 answer
1
847 views
Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$.
asked Sep 16, 2014 in DS Kathleen 847 views
31 votes
5 answers
2
6.5k 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}$
asked Sep 16, 2014 in Graph Theory Kathleen 6.5k views
18 votes
3 answers
3
5.8k views
In the absolute addressing mode: the operand is inside the instruction the address of the operand in inside the instruction the register containing the address of the operand is specified inside the instruction the location of the operand is implicit
asked Sep 16, 2014 in CO and Architecture Kathleen 5.8k views
18 votes
1 answer
4
2.2k views
The optimal page replacement algorithm will select the page that Has not been used for the longest time in the past Will not be used for the longest time in the future Has been used least number of times Has been used most number of times
asked Sep 16, 2014 in Operating System Kathleen 2.2k views
...