I know that the Binary Search algorithm has a Big-O of logN,but does this hold t

Question

I know that the Binary Search algorithm has a Big-O of logN,but does this hold true when the search is implemented with adoubly linked list instead of an array?

I want to say yes because the part of the linked list that you willtraverse is going to be halved after each data comparison. However, you still need to traverse a lot more elements in a linkedlist than a data structure with random access like an array. Is this difference so small that it really doesn't effect thealgorithms efficiency?

Any help would be greatly appreciated. :)

Explanation / Answer

Dear, It will not be log(n).
Reason: that's true , the part ofthe linked list that you will traverse is going to be halved aftereach data comparison. But you can see that if the element is after2nd half, then you will need to search n/2 elements. Which will beO(n). but in binary search , we get thisdecision in O(1) (just check the middle index value) . hence it isO(lg n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---