Is it possible for a search algorithm for linked lists to be O(log n)? From my understanding, linked lists could have either O(n) or O(1) since you can choose where to start, from the start of the link list to the end. Knowing this, can you start in the middle for a searching algorithm that runs in O(log n) time?
2 Answers
It is only possible to achieve faster than O(n) traversal if you can skip reading elements somehow, which is not possible unless you have some way of knowing beforehand what to skip and have additional structure to jump to parts of the list. If you started at the start or the end, you would have to search on average n/2 elements before finding what you are looking for. If you had exactly one pointer to the middle of the list, you would still have to search n/2 in each direction, which doesn't help. What's needed is more structure, such as imposing a sorted criterion. Then it is possible to implement this "skipping" in O(n) space and search in O(log n) time by implementing O(log n) "skip lanes" for the average case. This data structure is called a skip list and it keeps fast O(log n) insertion. These are the same asymptotic bounds as balanced trees, but are closer to linked lists in concept.
An O(log n) algorithm would require to
- divide the list into a fixed number of parts in constant time, and
- determine in which of the parts the searched item is in constant time.
e.g. for a binary search algorithm for a sorted indexed array data structure which keeps track of its size, the split point can be calculated directly from the size of the array, and it can be determined whether the searched item is in the first or second half by a comparison with the item at the split point.
But for a linked list, you don't know its size and would have to traverse it in order to find the split points. This is an O(n) operation, so the overall algorithm can't be O(log n).
In general, the second requirement is also not satisfied.
Related