Data Structures — GATE CS Formula Sheet
All key complexities, properties, and formulae consolidated for last-minute GATE revision.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
How to Use This Sheet
- Revise this page 24–48 hours before your exam for rapid recall.
- Cover each table and try to recall the values before looking.
- Focus on entries marked — these are frequent GATE sources.
1. Arrays & Strings
1D: Address of A[i] = B + w × i
2D Row-major: B + w × (i × C + j)
2D Col-major: B + w × (j × R + i)
With lower bounds Lr, Lc: substitute (i−Lr), (j−Lc); C = Uc−Lc+1
KMP: O(n+m) time, O(m) space Naive: O(nm) worst
Rabin-Karp: O(n+m) avg, O(nm) worst
2D Row-major: B + w × (i × C + j)
2D Col-major: B + w × (j × R + i)
With lower bounds Lr, Lc: substitute (i−Lr), (j−Lc); C = Uc−Lc+1
KMP: O(n+m) time, O(m) space Naive: O(nm) worst
Rabin-Karp: O(n+m) avg, O(nm) worst
2. Linked Lists
| Operation | Singly LL | Doubly LL |
|---|---|---|
| Access index i | O(n) | O(n) |
| Insert/Delete at head | O(1) | O(1) |
| Delete given pointer | O(n) | O(1) |
| Reversal (iterative) | O(n) time, O(1) space | O(n) time, O(1) space |
Floyd cycle detection: O(n) time, O(1) space
Merge sort on LL: O(n log n) time, O(log n) space
Merge sort on LL: O(n log n) time, O(log n) space
3. Stacks & Queues
Stack/Queue push/pop/enqueue/dequeue: O(1)
Circular queue: full ⇔ (rear+1)%cap == front; empty ⇔ front==rear
Infix→Postfix (shunting-yard): O(n)
Postfix/Prefix evaluation: O(n)
Queue from 2 stacks: O(1) amortised per operation
Stack from 2 queues: O(n) for push or pop (depending on variant)
Circular queue: full ⇔ (rear+1)%cap == front; empty ⇔ front==rear
Infix→Postfix (shunting-yard): O(n)
Postfix/Prefix evaluation: O(n)
Queue from 2 stacks: O(1) amortised per operation
Stack from 2 queues: O(n) for push or pop (depending on variant)
4. Trees
Max nodes at height h: 2h+1−1 Min nodes: h+1
Complete BT height: ⌊log2n⌋
Full BT: n0 = n2+1 (leaves = 2-child nodes + 1)
Full BT leaves = (n+1)/2 where n = total nodes
Number of distinct BSTs with n keys = Catalan(n) = C(2n,n)/(n+1)
Complete BT height: ⌊log2n⌋
Full BT: n0 = n2+1 (leaves = 2-child nodes + 1)
Full BT leaves = (n+1)/2 where n = total nodes
Number of distinct BSTs with n keys = Catalan(n) = C(2n,n)/(n+1)
| Traversal | Order | Key property |
|---|---|---|
| Inorder | L→N→R | Sorted output for BST |
| Preorder | N→L→R | Tree serialisation |
| Postorder | L→R→N | Deletion, expression eval |
| Level-order | BFS | Shortest path (unweighted) |
BST ops: O(h) where h = O(log n) avg, O(n) worst (skewed)
AVL: h ≤ 1.44 log2(n+2). Min nodes N(h) = N(h-1)+N(h-2)+1, N(0)=1, N(1)=2
AVL insert: at most 1 rotation. AVL delete: up to O(log n) rotations.
AVL: h ≤ 1.44 log2(n+2). Min nodes N(h) = N(h-1)+N(h-2)+1, N(0)=1, N(1)=2
AVL insert: at most 1 rotation. AVL delete: up to O(log n) rotations.
5. Heaps
1-indexed: parent=⌊i/2⌋, left=2i, right=2i+1
0-indexed: parent=⌊(i-1)/2⌋, left=2i+1, right=2i+2
Last internal node (1-indexed): ⌊n/2⌋
Insert: O(log n) Extract-max: O(log n) Peek: O(1)
Build-heap (bottom-up): O(n) NOT O(n log n)
Heap sort: O(n log n), in-place, not stable
d-ary heap: Insert O(logdn), Extract O(d logdn)
0-indexed: parent=⌊(i-1)/2⌋, left=2i+1, right=2i+2
Last internal node (1-indexed): ⌊n/2⌋
Insert: O(log n) Extract-max: O(log n) Peek: O(1)
Build-heap (bottom-up): O(n) NOT O(n log n)
Heap sort: O(n log n), in-place, not stable
d-ary heap: Insert O(logdn), Extract O(d logdn)
6. Hashing
Load factor α = n/m (n=keys, m=slots)
Chaining — Successful: 1+α/2 Unsuccessful: 1+α
Open addressing — Unsuccessful: 1/(1−α)
Linear probing — Unsuccessful: ½(1+1/(1−α)²)
Double hashing: h(k,i)=(h1(k)+i×h2(k)) mod m; h2(k)≠0
Typical: m=prime, h2(k)=1+(k mod (m-1))
Chaining — Successful: 1+α/2 Unsuccessful: 1+α
Open addressing — Unsuccessful: 1/(1−α)
Linear probing — Unsuccessful: ½(1+1/(1−α)²)
Double hashing: h(k,i)=(h1(k)+i×h2(k)) mod m; h2(k)≠0
Typical: m=prime, h2(k)=1+(k mod (m-1))
7. Graphs
| Operation | Adj. Matrix | Adj. List |
|---|---|---|
| Space | O(V²) | O(V+E) |
| Edge check | O(1) | O(degree) |
| BFS / DFS time | O(V²) | O(V+E) |
Handshaking: ∑degree = 2|E| (undirected)
Tree: n vertices, n−1 edges, connected, acyclic
Topological sort: exists ⇔ DAG. Time O(V+E).
Cycle detection (directed): DFS back edge (GRAY vertex). Undirected: visited non-parent.
Tree: n vertices, n−1 edges, connected, acyclic
Topological sort: exists ⇔ DAG. Time O(V+E).
Cycle detection (directed): DFS back edge (GRAY vertex). Undirected: visited non-parent.
8. Advanced Trees
B-tree order m: max m−1 keys/node, min ⌈m/2⌉−1 keys (non-root)
B-tree height: O(logmn)
Max keys in B-tree height h: mh+1−1
B-tree height: O(logmn)
Max keys in B-tree height h: mh+1−1
Red-Black tree: h ≤ 2log2(n+1). At most 2 rotations on insert, 3 on delete.
AVL vs RBT: AVL shorter, faster lookup. RBT fewer rotations, better writes.
Segment tree: O(n) build, O(log n) query & update, O(4n) space
Fenwick BIT: O(log n) prefix sum & update, O(n) space, 1-indexed only
Trie search/insert: O(m) for string of length m
9. Quick Reference: Sorting Algorithms
| Algorithm | Best | Avg | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Radix sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Yes |