What is the complexity of a circular doubly linked list using binary search?

Question

Is it O(n log n) or O(log n)?

Answer 1

Binary search requires random access, hence it's not possible on a linked list. You're stuck with an O(n) linear search.

Answer 2

I'm going to say it's not O(log n) because binary searches don't work well on linked lists - you don't have efficient random access.

If you really tried to do binary search, it would take O(log n) steps, but in each step, you need an O(n) traversal to access the desired element. So you could say it's O(nlog(n)).

You should just do a O(n) linear search instead.