Complexity comparison

Arrays win on indexed access and traversal because their elements are contiguous: O(1) reads and few cache misses. Linked lists win only on insertion or removal at a position you already hold, where an array must shift elements. In practice, even such workloads often favour arrays until n is very large.

Count the memory reads for reaching element k in the animation.

1static int getFromArray(int[] arr, int k) {
2    return arr[k];                      // address = base + k * 4: one memory read
3}
4
5static int getFromList(Node head, int k) {
6    Node cur = head;
7    for (int i = 0; i < k; i++) {
8        cur = cur.next;                 // pointer chase: one read per hop
9    }
10    return cur.value;
11}

A hash table gives expected O(1) get, put and remove when the hash function spreads keys evenly and the load factor is bounded. In the worst case all keys land in one bucket: O(n) for a list-based bucket, O(log n) for Java 8+ HashMap, which converts long buckets to balanced trees. Resizing costs O(n) occasionally but is amortised O(1).

Adversarial or poorly distributed keys are the practical risk; mutable keys and missing hashCode implementations are the common bugs.

A balanced binary search tree keeps its height O(log n) with rotations, so search, insert and delete are O(log n) in the worst case, and keys stay in sorted order for range and nearest-key queries. AVL trees have height at most about 1.44 log₂ n and red-black trees at most 2 log₂(n + 1); Java's TreeMap is a red-black tree.

An unbalanced tree degrades to a chain of height n on sorted input.

Any algorithm that sorts only by comparing elements needs Ω(n log n) comparisons in the worst case. A sorting algorithm is a binary decision tree whose leaves are the possible orderings; there are n! of them, and a binary tree with n! leaves has height at least log₂(n!) = Θ(n log n). So merge sort and heap sort are asymptotically optimal among comparison sorts.

Non-comparison sorts (counting, radix, bucket) escape the bound by using the structure of the keys. The chart compares measured growth of the quadratic and n log n sorts.

An adjacency matrix is a V × V array: O(V²) memory, O(1) test for an edge, O(V) to list the neighbours of a vertex. An adjacency list stores each vertex's neighbours: O(V + E) memory, O(degree) edge test and O(degree) neighbour listing. Use the matrix for dense graphs (E close to V²) or when constant-time edge checks matter; use lists for sparse graphs, which are the majority.

A road network with 10⁶ intersections and 3 × 10⁶ roads fits as a list but would need 10¹² cells as a matrix.

1int V = 4;
2boolean[][] matrix = new boolean[V][V];
3List<List<Integer>> list = new ArrayList<>();
4for (int i = 0; i < V; i++) list.add(new ArrayList<>());
5int[][] edges = {{0, 1}, {1, 2}, {2, 3}};
6for (int[] e : edges) { matrix[e[0]][e[1]] = matrix[e[1]][e[0]] = true; list.get(e[0]).add(e[1]); list.get(e[1]).add(e[0]); }