Data structures and algorithms: 50 Big-O flashcards

All 50 cards

1. 1
   Access an array element by index
   $O(1)$
2. 2
   Append to a dynamic array (Python list, JS array, Vec)
   Amortized $O(1)$

   An occasional resize copies everything, but doubling the capacity spreads that cost out.
3. 3
   Insert at the front of an array
   $O(n)$, because every element shifts
4. 4
   Search an unsorted array
   $O(n)$
5. 5
   Access the k-th node of a linked list
   $O(n)$, you have to walk from the head
6. 6
   Insert or delete at the head of a linked list
   $O(1)$
7. 7
   Hash map lookup, insert and delete
   $O(1)$ on average, $O(n)$ in the worst case (many collisions)
8. 8
   Two ways hash tables resolve collisions
   Chaining (a list per bucket) and open addressing (probe for another slot)
9. 9
   Binary heap: push, pop and peek
   Push and pop $O(\log n)$, peek at the min/max $O(1)$
10. 10
    Build a heap from n unsorted items
    $O(n)$ with bottom-up heapify

    Pushing items one by one would take $O(n \log n)$.
11. 11
    Balanced BST search, insert, delete
    $O(\log n)$

    An unbalanced BST can degrade to $O(n)$, like a linked list.
12. 12
    What order does an in-order traversal of a BST visit keys in?
    Sorted (ascending) order
13. 13
    Trie lookup for a word of length L
    $O(L)$, independent of how many words are stored
14. 14
    Space of an adjacency list vs an adjacency matrix
    List $O(V + E)$; matrix $O(V^2)$
15. 15
    Time of BFS or DFS on a graph (adjacency list)
    $O(V + E)$
16. 16
    Shortest path in an unweighted graph
    Breadth-first search from the source
17. 17
    Merge sort: time, space, stable?
    $O(n \log n)$ in every case, $O(n)$ extra space, stable
18. 18
    Quicksort: average and worst case
    Average $O(n \log n)$, worst $O(n^2)$ (bad pivots); not stable
19. 19
    Heapsort: time, space, stable?
    $O(n \log n)$, $O(1)$ extra space, not stable
20. 20
    Insertion sort: best and worst case
    Best $O(n)$ on nearly sorted input, worst $O(n^2)$; stable
21. 21
    Lower bound for comparison-based sorting
    $\Omega(n \log n)$ comparisons in the worst case
22. 22
    Counting sort complexity
    $O(n + k)$ for keys in a range of size $k$; not comparison-based
23. 23
    What does “stable sort” mean?
    Elements that compare equal keep their original relative order
24. 24
    Which algorithm do Python’s sorted and Java’s object sort use?
    Timsort: stable, $O(n \log n)$ worst case, $O(n)$ on already-sorted runs
25. 25
    Binary search time and precondition
    $O(\log n)$, and the array must be sorted
26. 26
    Binary search midpoint that can’t overflow
    mid = lo + (hi - lo) // 2

    In fixed-width integer languages, (lo + hi) / 2 can overflow.
27. 27
    Two pointers: find a pair with a given sum in a sorted array
    Start at both ends; move left up if the sum is too small, right down if too big. $O(n)$ time, $O(1)$ space
28. 28
    Sliding window: longest substring without repeating characters
    Grow the right edge, shrink the left while a character repeats, track positions in a map. $O(n)$
29. 29
    Detect a cycle in a linked list in O(1) space
    Floyd’s tortoise and hare: a slow and a fast pointer meet if there’s a cycle. $O(n)$ time
30. 30
    Dijkstra’s algorithm with a binary heap
    $O((V + E) \log V)$; requires non-negative edge weights
31. 31
    Shortest paths with negative edge weights
    Bellman–Ford, $O(VE)$; it also detects negative cycles
32. 32
    Topological sort: when does it exist, and how fast is it?
    Only for a DAG (no cycles). Kahn’s algorithm or DFS runs in $O(V + E)$
33. 33
    Union-find with path compression and union by rank
    Nearly constant amortized time per operation: $O(\alpha(n))$
34. 34
    Kruskal’s minimum spanning tree
    Sort edges by weight and add them unless they form a cycle (checked with union-find). $O(E \log E)$
35. 35
    Memoization vs tabulation
    Memoization is top-down recursion with a cache; tabulation fills a table bottom-up
36. 36
    Naive recursive Fibonacci vs memoized
    Naive $O(2^n)$; memoized or iterative $O(n)$
37. 37
    Longest common subsequence of strings of lengths m and n
    $O(mn)$ time with a DP table
38. 38
    0/1 knapsack with n items and capacity W
    $O(nW)$: pseudo-polynomial, since $W$ is a value, not an input size
39. 39
    Edit (Levenshtein) distance between strings of lengths m and n
    $O(mn)$ dynamic programming
40. 40
    Space cost of recursion
    One stack frame per level: $O(\text{depth})$, e.g. $O(n)$ for naive recursion over a list
41. 41
    What is amortized analysis?
    The average cost per operation over a worst-case sequence of operations, even if single operations are sometimes expensive
42. 42
    Big-O vs Big-Θ vs Big-Ω
    O is an upper bound, Ω a lower bound, Θ a tight bound (both)
43. 43
    Solve $T(n) = 2T(n/2) + O(n)$
    $O(n \log n)$, as in merge sort (master theorem)
44. 44
    Find the k largest of n items
    Keep a min-heap of size $k$: $O(n \log k)$

    Quickselect finds the k-th largest in $O(n)$ on average.
45. 45
    Design an LRU cache with O(1) get and put
    A hash map from key to node plus a doubly linked list ordered by recency
46. 46
    Prefix sums
    Precompute running totals in $O(n)$, then answer any range sum in $O(1)$

    python

    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    range_sum = prefix[r + 1] - prefix[l]

47. 47
    Next greater element for every item
    A monotonic stack: $O(n)$, each item is pushed and popped once
48. 48
    Time to generate all permutations of n items
    $O(n \cdot n!)$
49. 49
    Deque operations at both ends
    $O(1)$ push and pop at either end
50. 50
    Height of a balanced binary tree with n nodes
    $O(\log n)$