What enters the problem?
Size, shape, constraints?
Algorithm choice depends on input scale and structure.
Side 36
Algorithms &
Data Structures
A study of how problems become representations and procedures. The same task can become easy or expensive depending on how information is organized and which operations the algorithm must perform.
problem→representation→structure→procedure→complexity
06structure families
05algorithm patterns
05complexity questions
36Side
Representation is often half the solution.
Before choosing an algorithm, define what must be stored, queried, updated and traversed.
What must be done repeatedly?
Lookup, insert, rank, traverse?
The dominant operation should influence the data structure.
How should information be stored?
Array, map, tree, graph?
Representation determines which operations become cheap or expensive.
What sequence solves the task?
Iterate, recurse, divide?
An algorithm is a finite rule for transforming input into output.
How does cost scale?
Time and space.
Correctness is necessary; scalability decides whether the method remains useful.
Data structures encode trade-offs.
No structure is universally best; each makes some operations fast by accepting costs elsewhere.
Contiguous indexed storage.
Fast random access; insertion in the middle can require shifting elements.
Nodes connected by references.
Flexible insertion and deletion; poor random access and locality.
Key → bucket mapping.
Very fast average lookup when hashing and load are well controlled.
Hierarchical structure.
Useful for ordered search, indexes, parsing and nested relationships.
Priority-oriented partial order.
Efficient access to the smallest or largest item without fully sorting all items.
Arbitrary relationships.
Represents networks, dependencies, routes and state transitions.
Algorithmic patterns recur across domains.
Learning patterns is more transferable than memorizing isolated procedures.
Split, solve, combine.
Works when large problems can be decomposed into smaller independent subproblems.
Take the best local step.
Works only when local choices can be proven to compose into a global optimum.
Reuse overlapping subproblems.
Store intermediate results so repeated computation becomes lookup.
Explore and undo.
Useful for combinatorial search when partial choices can be rejected early.
Define a problem in terms of smaller versions.
Elegant when the data or problem is naturally hierarchical.
Systematically visit structure.
Breadth-first and depth-first search expose different reach and memory behaviors.
Ordering and lookup expose core algorithmic trade-offs.
Simple tasks reveal how representation, guarantees and input structure affect performance.
| Method | Core idea | Typical time | Useful when |
|---|---|---|---|
| Linear search | Check sequentially | O(n) | Data are small or unsorted |
| Binary search | Halve search interval | O(log n) | Data are ordered and indexable |
| Merge sort | Split and merge sorted halves | O(n log n) | Stable predictable sorting is useful |
| Quicksort | Partition around pivot | O(n log n) average | Fast in-memory sorting with good implementation |
| Heap sort | Repeated priority extraction | O(n log n) | Strong worst-case bound with low extra space |
Complexity describes growth, not stopwatch time.
Asymptotic analysis asks how resource use changes as input grows.
O(1)
Constant growth.
Cost stays bounded independent of input size.
O(log n)
Repeatedly shrink the search space.
Typical of balanced trees and binary search.
O(n)
Touch each item once.
Often unavoidable when all input must be inspected.
O(n log n)
Efficient comparison sorting territory.
Appears when logarithmic levels each process n work.
O(n²)+
Pairwise or combinatorial growth.
Can become prohibitive quickly as inputs scale.
Design lab.
Choose the representation before reaching for code.
You need the most frequent 10 items in a huge stream.
Think hash table for counts plus a small heap for top-k maintenance rather than repeatedly sorting the entire dataset.
You need shortest paths across a road network.
Represent intersections as nodes and roads as weighted edges; use graph algorithms rather than forcing the problem into a flat table.
You need fast membership tests with frequent updates.
A hash set is usually a stronger default than scanning an array repeatedly, assuming exact membership and memory trade-offs are acceptable.
You need to repeatedly ask for the next highest-priority task.
Use a priority queue / heap rather than keeping the entire collection fully sorted after each update.
Introduction to AlgorithmsCormen et al. · comprehensive foundation
AlgorithmsSedgewick & Wayne · implementation and analysis
The Algorithm Design ManualSteven Skiena · design patterns
Data Structures and Algorithms in PythonGoodrich et al. · practical structures