Learn CS at a glance.
Read faster. Revise smarter.

Why does traversing a contiguous array of size N typically outperform traversing a singly linked list of the same size, even though both operations have an O(N) time complexity?

Array elements are stored in contiguous memory locations, which maximizes CPU cache locality and allows the system to prefetch data efficiently. In contrast, linked list nodes are scattered across memory, causing frequent cache misses as the CPU must repeatedly look up pointer addresses.

In a hash table, why does the search performance of Open Addressing (like linear probing) degrade much faster than Separate Chaining as the load factor approaches 1?

As the load factor approaches 1, Open Addressing suffers from clustering, where long runs of occupied slots form and drastically increase the number of probes needed to find an empty slot. Separate Chaining handles collisions by appending to lists, meaning lookup time degrades gradually relative to the average list length rather than failing to locate a slot.

For a deeply nested, narrow tree (e.g., a degenerate tree of depth N and width 1), would BFS or DFS require less auxiliary space, and why?

BFS would require less auxiliary space, specifically O(1) memory, because its queue will hold at most one node at any given level. In contrast, DFS would require O(N) auxiliary space because its recursion stack must store all N ancestor nodes from the root to the leaf.