Data Structures & Algorithms
Essential CS concepts for technical interviews and coursework
IT & Tech Reports | Class IM24A | 2026
1. Big-O Complexity
Big-O notation describes how an algorithm's time or space requirements grow with input size n. Always
aim for the lowest complexity feasible.
Notation Name Example
O(1) Constant Hash map lookup
O(log n) Logarithmic Binary search
O(n) Linear Array scan
O(n log n) Linearithmic Merge sort, heap sort
O(n^2) Quadratic Bubble sort, nested loops
O(2^n) Exponential Recursive subset enumeration
O(n!) Factorial Brute-force permutations
2. Arrays & Linked Lists
Operation Array Linked List
Access by index O(1) O(n)
Insert at end O(1) amortised O(1) with tail pointer
Insert at front O(n) O(1)
Delete middle O(n) O(n) find + O(1) delete
Memory Contiguous block Scattered (pointer overhead)
3. Stacks & Queues
• Stack (LIFO) — push/pop from same end. Used for: call stack, undo history, DFS
• Queue (FIFO) — enqueue at back, dequeue from front. Used for: BFS, task queues, print spoolers
• Deque — double-ended queue, supports O(1) at both ends
• Priority Queue (Heap) — always dequeue the min/max element. Used for: Dijkstra, scheduling
4. Hash Maps (Dictionaries)
Hash maps store key-value pairs with O(1) average-case lookup, insert, and delete. Collisions are
resolved via chaining or open addressing.
• Python dict, JavaScript Object/Map, Java HashMap all implement hash maps
• Worst case is O(n) due to collisions — rare with good hash functions
• Load factor = items / buckets; rehash when load factor > 0.75
5. Trees
Tree Type Key Property Use case
Binary Tree Each node has at most 2 children General hierarchical data
BST Left < Node < Right Sorted data, O(log n) search
AVL / Red-Black Self-balancing BST Databases, sorted maps
Heap Parent <= children (min-heap) Priority queues, heap sort
Trie Characters on edges Autocomplete, spell check
B-Tree Many children, optimised for disk Database indexes
6. Graph Algorithms
Graphs consist of vertices (nodes) and edges (connections). They can be directed or undirected,
weighted or unweighted.
Algorithm Type Use case Complexity
BFS Traversal Shortest path (unweighted) O(V+E)
DFS Traversal Cycle detection, topological sort O(V+E)
Dijkstra Shortest path Weighted graphs (non-negative) O((V+E) log V)
Bellman-Ford Shortest path Negative edge weights O(VE)
Kruskal / Prim MST Minimum spanning tree O(E log E)
7. Sorting Algorithms
Algorithm Best Average Worst Stable?
Bubble Sort O(n) O(n^2) O(n^2) Yes
Insertion Sort O(n) O(n^2) O(n^2) Yes
Merge Sort O(n log n) O(n log n) O(n log n) Yes
Quick Sort O(n log n) O(n log n) O(n^2) No
Heap Sort O(n log n) O(n log n) O(n log n) No
Algorithm Best Average Worst Stable?
Tim Sort O(n) O(n log n) O(n log n) Yes
8. Dynamic Programming
DP solves complex problems by breaking them into overlapping subproblems, storing results to avoid
redundant computation (memoisation or tabulation).
• Identify: overlapping subproblems + optimal substructure
• Top-down (memoisation): recursive + cache results in a dict
• Bottom-up (tabulation): fill a table iteratively from base cases
• Classic DP problems: Fibonacci, knapsack, longest common subsequence, coin change