Foundations
dsa.fetehadin.com1.1 What Is a Data Structure?
A data structure is a way of organising data in memory so the operations you need are fast. Learn how they are classified and what makes a good one.
| Array: read item i | O(1) |
| Array: insert at the front | O(n): shift everything |
| Linked list: insert at the front | O(1) |
| Linked list: read item i | O(n): walk from the head |
- ✗Calling a stack "non-linear". Stacks and queues are linear; only trees and graphs are non-linear here.
- ✗Saying an array is dynamic. A C++ array has a fixed size;
vectorand linked lists are dynamic. - ✗Confusing a data structure (how data is stored) with an algorithm (the steps that use it).
1.2 ADTs & Abstraction
An Abstract Data Type says WHAT operations exist; a data structure says HOW they are built. Separating the two is the key idea behind every structure on this roadmap.
| push / pop / top (array implementation) | O(1) |
| push / pop / top (linked implementation) | O(1) |
| Maximum size | array: fixed · linked list: limited only by memory |
- ✗Saying an ADT "is" an array. An ADT has no storage details at all; an array can only implement one.
- ✗Listing implementation details (like
topindex) as part of the ADT's definition. - ✗Forgetting error conditions. "pop on an empty stack is an error" IS part of the ADT.
1.3 Pointers, new/delete & the Heap
A pointer holds an address. new asks the heap for memory that lives until you delete it. Master this and linked lists become easy.
&x, *p, p->field | O(1) |
new / delete one object | O(1) (amortised; done by the allocator) |
| Stack memory | automatic: freed when the function returns |
| Heap memory | manual: lives until delete |
- ✗Dereferencing
nullptror an uninitialised pointer, which crashes (segmentation fault). - ✗Using memory after
delete(dangling pointer). Set the pointer tonullptrright after. - ✗
new[]paired withdeleteinstead ofdelete[].
1.4 Recursion Primer
A function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Phase 4) and merge/quick sort (Phase 3).
| factorial(n): time | O(n): n calls, O(1) work each |
| factorial(n): space | O(n) stack frames |
| recursive binary search: time | O(log n) |
| recursive binary search: space | O(log n) stack frames (iterative version: O(1)) |
- ✗No base case, or a base case that is never reached (e.g.
factorial(n + 1)). - ✗Forgetting to
returnthe recursive call's result (bs(...)instead ofreturn bs(...)). - ✗Thinking recursion is always slower or always better. It trades stack memory for simpler code.
1.5 Algorithms & Their Properties
An algorithm is a finite, unambiguous sequence of steps that solves a problem. Learn the 11 properties every correct algorithm must have.
| findMax: comparisons | exactly n − 1 |
| findMax: time | O(n), and best = worst |
| Space | O(1) |
- ✗Confusing definiteness (each step has one clear meaning) with finiteness (the algorithm stops).
- ✗Saying an algorithm needs at least one input. It needs zero or more inputs but at least one output.
- ✗Treating "a program" and "an algorithm" as the same. A program may run forever (an OS); an algorithm must terminate.
1.6 Measuring Efficiency
Empirical vs theoretical analysis, qualitative vs quantitative, the three classic avoidable inefficiencies, and the time–space trade-off.
| Search with late termination | always n checks |
| Search that breaks early | 1 … n checks |
| Duplicate check with nested loops | O(n²) time, O(1) space |
| Duplicate check with a set | O(n) time, O(n) space ← trade-off |
- ✗Saying empirical analysis is useless. It is useful, but its results depend on the machine, compiler, language and inputs.
- ✗Mixing up "redundant computation" (recomputing the same value in a loop) with "repeated array referencing" (reading
a[i]many times). - ✗Thinking the faster algorithm is always better. It may need far more memory.
1.7 Counting Time Units
Turn code into a formula T(n) using a simple set of counting rules. Loops become sums, and nested loops multiply.
Single loop for(i=0;i<n;i++) k=k+1; cout<<k; | T(n) = 4n + 3 → O(n) |
Nested n × n loop with k++ | T(n) = 3n² + 4n + 3 → O(n²) |
Loop where i doubles (i *= 2) | ≈ log₂ n iterations → O(log n) |
- ✗Counting the loop test n times instead of n + 1 (the last, failing test counts too).
- ✗Counting
k = k + 1as 1 unit. It is 2: one addition and one assignment. - ✗For
if/else, adding both branches. Count the condition plus the larger branch only.
1.8 Best, Average & Worst Case
The same algorithm can be fast or slow depending on the input. We analyse the best, average and worst case, and usually report the worst.
| Linear search: best (key is first) | O(1): 1 comparison |
| Linear search: average (key present) | (n + 1) / 2 comparisons → O(n) |
| Linear search: worst (last or missing) | n comparisons → O(n) |
| Bubble sort with flag: best / worst | O(n) / O(n²) |
| Space | O(1) |
- ✗"Best case is when n is small." No: best case is about the arrangement of the input for a given n, never about a small n.
- ✗Thinking the average case is (best + worst) / 2. It is an expected value over all inputs.
- ✗Mixing up the case with the notation. "Worst case" is not the same thing as "Big-O".
1.9 Asymptotic Notation & Big-O Proofs
O, Ω, Θ, o and ω describe how fast T(n) grows for large n. Learn the definitions, the order of growth, and how to prove f(n) = O(g(n)) by finding c and k.
| O(1) | constant: array access, push/pop |
| O(log n) | logarithmic: binary search |
| O(n) | linear: linear search, traversal |
| O(n log n) | linearithmic: merge sort, heap sort |
| O(n²) | quadratic: bubble, selection, insertion sort |
| O(n³) | cubic: three nested loops |
| O(2ⁿ) | exponential: all subsets, naive Fibonacci |
- ✗Forgetting to state c and k explicitly. A proof without numbers gets partial marks.
- ✗Claiming 3n² = O(n). False: no constant c makes 3n² ≤ c·n for all large n.
- ✗Thinking Big-O means "worst case". Big-O is an upper bound on a function; you can give an upper bound for the best case too.
- Data structure:
- A way of organising data in memory so that the operations you need are efficient.
- Primitive data structure:
- Built-in types operated on directly by the machine: int, char, float, bool, pointers.
- Linear data structure:
- Items form a sequence, each with at most one predecessor and one successor: arrays, linked lists, stacks, queues.
- Non-linear data structure:
- Items branch or connect freely: trees and graphs.
- Static vs dynamic:
- Static structures have a size fixed when they are created (arrays); dynamic ones grow and shrink at run time (linked lists).
- ADT (Abstract Data Type):
- A description of data plus the operations on it, saying what they do but not how they are implemented.
- Abstraction:
- Hiding implementation details behind an interface so users only see what they need.
- Algorithm:
- A finite, well-defined sequence of steps that turns input into the desired output.
- Finiteness:
- An algorithm must stop after a finite number of steps.
- Definiteness:
- Every step is precise and unambiguous.
- Empirical analysis:
- Measuring an algorithm by running it and timing it. Depends on the machine and the input.
- Theoretical analysis:
- Counting basic operations as a function of input size n. Machine-independent.
- Time unit:
- One basic operation (assignment, single I/O, Boolean or arithmetic op, return) counted as 1 in T(n).
- T(n):
- The running time of an algorithm as a function of input size n, in time units.
- Best / average / worst case:
- The running time on the most favourable, typical, and least favourable input of size n.
- Big-O (O):
- Upper bound: f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ k, for some constants c > 0 and k.
- Big-Omega (Ω):
- Lower bound: f(n) ≥ c·g(n) for all n ≥ k.
- Big-Theta (Θ):
- Tight bound: f(n) is both O(g(n)) and Ω(g(n)).
- Little-o / little-omega:
- Strict bounds: f grows strictly slower (o) or strictly faster (ω) than g.
- Time/space trade-off:
- Using more memory to save time (or the reverse), e.g. storing results instead of recomputing them.
- Recursion:
- A function that calls itself on a smaller input, stopping at a base case.
- Base case:
- The input a recursive function answers directly, without recursing.
- Call stack:
- Memory where each active function call keeps its parameters and local variables.
- Pointer:
- A variable that stores a memory address.
- Heap (memory):
- Memory for dynamic allocation with new/delete. Lives until you free it.
- Memory leak:
- Heap memory that is no longer reachable but was never deleted.
- Dangling pointer:
- A pointer to memory that has already been freed.