Runtime complexity of sorted singly linked list and sorted doubly linked list

Question

The average and worst runtime of insertion and search in a sorted singly and doubly linked list is O(1) and O(n). Are the runtime complexities same in the best case?

In other words, in the best case, does a sorted singly and doubly linked list has O(1) time for insertion and O(n) time for search?

Answer 1

Think about it like this:

In the best case, when you're searching, the first element you look at is the one you want, so you're done (this is the case with a lot of searching algorithms, actually). This is independent of the length of the linked list, i.e. it takes the same amount of time no matter how long the linked list is, so it's O(1).

Insertion after a particular element is the same in the best case: You insert after a particular element, which again is independent of the length of the list, so it's O(1).

I should note that runtime complexities in the best case aren't very interesting, since in the best case everything usually goes pretty fast. People usually only talk about average case runtimes because close to the average case will happen often, and worst because you want to be aware of whether your algorithm will do really really badly sometimes.

• JParkDS: Thank you so very much! This really clarifies my question.
• CoffeeTableEspresso: @JParkDS glad to help. Please accept my answer (click the check mark, it should turn green) if it helped you, or let me know if anything is still unclear.
• JParkDS: one follow-up question - this means that both singly and doubly linked list would have O(1) time for search and insert - right?
• CoffeeTableEspresso: In my answer, whatever I said about "linked lists" applies to both. The difference between singly linked and doubly linked only matters if you have to traverse the linked list backwards