Context

Understanding time complexity is essential for choosing the right data structure in coding interviews and production systems. Interviewers often expect candidates to compare common structures and justify trade-offs.

Core Question

Describe the time complexities of common data structures, focusing on arrays, linked lists, hash tables, stacks, queues, heaps, and trees. In your answer:

1. Explain the typical time complexity for access, search, insertion, and deletion.
2. Distinguish between average-case, worst-case, and amortized complexity where relevant.
3. Discuss why the complexity differs across structures based on their internal organization.

Scope Guidance

You do not need to derive formal proofs, but you should give a clear interview-level explanation of how these structures behave, when one is preferred over another, and the common pitfalls in oversimplifying complexity claims such as saying a hash table is always O(1).

Average vs Worst Case

Many data structures have different average and worst-case behavior. For example, a hash table is typically O(1) for lookup on average, but can degrade to O(n) in the worst case if many keys collide.

Amortized Complexity

Amortized complexity describes the average cost of an operation over a sequence of operations. Dynamic arrays are the classic example: append is usually O(1), but occasional resizing makes some individual appends O(n), leading to amortized O(1).

arr = []
for x in range(n):
    arr.append(x)  # amortized O(1)

Contiguous vs Pointer-Based Storage

Arrays store elements contiguously, which enables O(1) indexing but makes insertion in the middle expensive. Linked lists use nodes connected by pointers, so insertion after a known node is O(1), but random access is O(n).

value = arr[i]      # O(1)
# linked list traversal to index i is O(n)

Balanced vs Unbalanced Trees

Tree operation complexity depends on height. Balanced trees keep height near log n, giving O(log n) search, insert, and delete, while unbalanced trees can degrade to O(n).

Heap Ordering

A heap is a partially ordered tree, not a fully sorted one. This is why finding the minimum or maximum is O(1), but searching for an arbitrary value is O(n).

import heapq
heap = [3, 1, 5]
heapq.heapify(heap)
smallest = heap[0]  # O(1)