How to apply binary search O(log n) on a sorted linked list?

by

It is certainly not possible with a plain singly-linked list.

Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a “next” pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and it takes a operation to follow it]. For certain inputs, it is necessary to examine the last node (specifically, if the searched-for element is equal to or greater than its value). Hence for certain inputs, time required is proportional to n.

You either need more time, or a different data structure.

Note that you can do it in O(log n) comparisons with a binary search. It’ll just take more time than that, so this fact is only of interest if comparisons are very much more expensive than list traversal.

More Related Contents:

  1. Find kth smallest element in a binary search tree in Optimum way
  2. What’s the fastest algorithm for sorting a linked list?
  3. Best algorithm to test if a linked list has a cycle
  4. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  5. Complexity of absolute difference and sum
  6. Big O, how do you calculate/approximate it?
  7. Reverse the ordering of words in a string
  8. How to create the most compact mapping n → isprime(n) up to a limit N?
  9. How to reverse a singly linked list using only two pointers?
  10. How can building a heap be O(n) time complexity?
  11. Hash table runtime complexity (insert, search and delete)
  12. How does finding a cycle start node in a cycle linked list work?
  13. What would cause an algorithm to have O(log log n) complexity?
  14. How do you validate a binary search tree?
  15. design a stack such that getMinimum( ) should be O(1)
  16. how to calculate binary search complexity
  17. Array remove duplicate elements
  18. What is the fastest way to find the closest point to a given point?
  19. insert, delete, max in O(1)
  20. In Order Successor in Binary Search Tree
  21. Algorithm for autocomplete?
  22. Big-oh vs big-theta [duplicate]
  23. graph – Dijkstra for The Single-Source Longest Path
  24. What is the advantage to using Bloom filters?
  25. Why does Dijkstra’s algorithm use decrease-key?
  26. Merging two sorted linked lists
  27. Search a sorted 2D matrix [duplicate]
  28. Algorithm for merging two max heaps?
  29. Why is vector array doubled?
  30. Computational complexity of base conversion

Leave a Comment