09
DSA + algorithms / Beginner → intermediate
DSA and Big-O foundations
How to choose data structures and reason about time/space complexity instead of memorizing implementations.
01Why DSA matters
Data structures define how information is arranged; algorithms define how it is processed. The right structure often makes the algorithm simpler and faster. Big-O describes how resource use grows as input size grows, not the exact runtime on one machine.
| Complexity | Typical example |
|---|---|
| O(1) | Array index / hash lookup average |
| O(log n) | Binary search |
| O(n) | Linear scan |
| O(n log n) | Efficient comparison sort |
| O(n²) | Nested all-pairs scan |
02Choose from operations
- Need ordered index access? Dynamic array/vector.
- Need FIFO? Queue/deque.
- Need LIFO? Stack/deque.
- Need fast key lookup? Hash table.
- Need ordered keys/range operations? Balanced tree.
- Need highest/lowest priority repeatedly? Heap.
- Need relationships/routes? Graph.
03Analyze loops
cppLinear scan
// O(n): each element is visited once.
int findMax(const std::vector<int>& values) {
int best = values.at(0);
for (int value : values) {
if (value > best) best = value;
}
return best;
}