Data Structures and Algorithms Cheat Sheet

Posted on May 14, 2026 in Computer Engineering

Big-O and Theta Notation

1 < log n < (log n)² < n < n log n < n² < n²log n < n³ < 2ⁿ

  • Θ (Theta): Tight bound/actual growth.
  • O (Big-O): Upper bound/worst-case.
  • Ω (Omega): Lower bound.

Note: Ignore constants and smaller terms. Example: 3n²+5n+1 = Θ(n²)

Loop Complexity Rules

  • i++ or i=i+2: O(n)
  • i=i*2 or i=i/2: O(log n)
  • Nested loops: Multiply complexities (e.g., O(n log n)).
  • Sequential loops: Add complexities (e.g., O(n) + O(log n) = O(n)).

Universal Loop Analysis

“Outer loop runs ___ times. Inner loop runs ___ times because ___. Since loops are nested/sequential, total runtime is ___.”

Searching Algorithms

  • Linear Search: Unsorted arrays allowed. Best O(1), Avg/Worst O(n).
  • Binary Search: Requires sorted array. Repeatedly halves search space. Best O(1), Avg/Worst O(log n). mid=(low+high)/2.

Sorting Algorithms

  • Insertion Sort: Best O(n), Avg/Worst O(n²). Efficient for nearly sorted data.
  • Selection Sort: Best/Avg/Worst O(n²).
  • Merge Sort: Divide-and-conquer. Best/Avg/Worst O(n log n).
  • Quick Sort: Pivot partitioning. Best/Avg O(n log n), Worst O(n²).

Recursion and Dynamic Programming

  • Recursion: Base case stops execution; recursive case solves smaller sub-problems.
  • Memoization: Save results to avoid recomputation.
  • Dynamic Programming (DP): Bottom-up table solution. Can reduce O(2ⁿ) to O(n).
  • Knapsack Problem: Maximize value within capacity. Formula: max(take, skip).
  • LCS (Longest Common Subsequence): Gaps allowed. If chars match, use them; else, branch.

Trees and Heaps

  • Binary Search Tree (BST): Left < parent < right.
  • BST Deletion: Leaf (remove), one child (replace), two children (use predecessor/successor).
  • AVL Trees: Self-balancing BST (height difference ≤ 1). Operations: O(log n).
  • Heaps: Min-heap (parent ≤ children). Insert (siftUp), deleteMin (siftDown). Array index: left=2i+1, right=2i+2.

Hash Tables

Hash function: h(k)=k mod m. Collisions handled via chaining or linear probing. Load factor α=n/m. Average lookup/insertion: O(1).

Graph Algorithms

  • DFS: Depth-first, uses stack/recursion.
  • BFS: Level-by-level, uses queue.
  • MST (Minimum Spanning Tree): Cheapest way to connect all vertices (n−1 edges).
  • Kruskal’s: Sort edges, use Union-Find to avoid cycles. O(E log E).
  • Dijkstra’s: Shortest path from source. Non-negative weights only. O(E log V).
  • Floyd-Warshall: All-pairs shortest paths. O(n³).
  • Graph Colouring: Assign colors so adjacent vertices differ.

Key Takeaways

  • log n: Divide/multiply by 2.
  • n²: Nested loops.
  • n log n: Divide-and-conquer.
  • DFS: Stack/recursion; BFS: Queue.
  • Dijkstra: Fails on negative weights.