Formula sheet

Every formula from every topic. Type to filter.

📚 Arrays, Stacks, Queues & Linked Lists

1-D address
addr(A[i]) = base + (i − lower) × size
2-D row-major
addr(A[i][j]) = base + ((i − r₀) × (#columns) + (j − c₀)) × size
2-D column-major
addr(A[i][j]) = base + ((j − c₀) × (#rows) + (i − r₀)) × size
Circular queue
next = (index + 1) mod n; count = (rear − front + n) mod n (when a slot is left empty)
Triangular matrix
n(n + 1)/2 stored elements

🌳 Trees & Binary Search Trees

Edges / leaves
edges = n − 1; n₀ = n₂ + 1; for a full k-ary tree with i internal nodes: n = k·i + 1, leaves = (k − 1)·i + 1
Height bounds (h in edges)
⌈log₂(n + 1)⌉ − 1 ≤ h ≤ n − 1; max nodes 2^(h+1) − 1
Number of binary trees / BSTs
Cₙ = C(2n, n)/(n + 1): 1, 1, 2, 5, 14, 42, 132 …
Traversals
pre: N L R; in: L N R; post: L R N; inorder(BST) = sorted
AVL minimum nodes
N(0) = 1 (or 0 for empty), N(1) = 2, N(h) = N(h − 1) + N(h − 2) + 1

⛰️ Heaps & Priority Queues

Indices (0-based)
left = 2i + 1; right = 2i + 2; parent = ⌊(i − 1)/2⌋. 1-based: 2i, 2i + 1, ⌊i/2⌋
Height / levels
height = ⌊log₂ n⌋; at most ⌈n / 2^(h+1)⌉ nodes of height h
Build-heap
Floyd (bottom-up): Θ(n); repeated insert: Θ(n log n)
Operations
insert O(log n); extract-max O(log n); find-max O(1); delete arbitrary known index O(log n)
Leaves
a heap of n nodes has ⌈n/2⌉ leaves

#️⃣ Hashing

Load factor
α = n / m
Chaining
unsuccessful: Θ(1 + α); successful: ≈ 1 + α/2; worst case O(n)
Open addressing (uniform hashing)
unsuccessful ≤ 1/(1 − α); successful ≤ (1/α) ln(1/(1 − α))
Probe sequences
linear: h + i; quadratic: h + c₁i + c₂i²; double: h₁ + i·h₂ (all mod m)
Collisions
expected number of colliding pairs among n keys in m slots ≈ n(n − 1)/(2m)