What are the worst-case, average-case, and best-case time complexities for searching a value in an unsorted singly linked list?

• A. Worst-case O(n); Average-case O(n); Best-case O(1)
• B. Worst-case O(n); Average-case O(n); Best-case O(1) if head contains the value
• C. Worst-case O(n^2); Average-case O(n); Best-case O(1)
• D. Worst-case O(1); Average-case O(n); Best-case O(n)

Answer: (B)

When you search for a value in an unsorted singly linked list, you have to check each node one by one because there’s no ordering to guide you to the target. The number of nodes you might need to inspect scales with the size of the list, n.

In the worst case you end up examining every node, either because the value is at the very end or not present at all. That gives a time complexity of O(n). On average, if the target is equally likely to be anywhere, you’d expect to check about half the nodes before finding it, which still grows linearly with n, so the average case is O(n). The best-case situation occurs when the very first node (the head) contains the value you’re looking for, so you finish after a constant amount of work, i.e., O(1). It’s important to note that this best-case condition is specific: it happens only if the head holds the value.

That’s why the best-supported answer states the worst and average cases as O(n) and the best case as O(1) specifically when the head contains the value. Options that claim quadratic time or omit the conditional best-case don’t reflect how a linear scan behaves in an unsorted list.