Programming Fundamentals
Time Complexity
Big-O notation describes how runtime or memory grows with input size while ignoring constants — O(1), O(log n), O(n), O(n log n), O(n²). It lets you compare algorithms independently of hardware and predict where code falls over at scale. Watch for hidden costs: a nested loop over the same data is O(n²), and that dies at a million rows.
Purpose
Big-O notation describes how an algorithm's runtime or memory grows as its input grows, ignoring constants and hardware — O(1), O(log n), O(n), O(n log n), O(n²). It exists so engineers can compare approaches abstractly and predict where code will fall over long before it does.
When to Use It
Use it when sizing a design for scale ('what happens at a million rows?'), when reviewing code for hidden nested loops, and when reading a database plan — an indexed lookup is O(log n) while a full scan is O(n). It is also the backbone of interview problem analysis.
Trade-offs
Big-O is asymptotic: it hides constants and memory locality, which dominate at small sizes — an O(n) pass with a heavy constant can lose to an O(n log n) sort on real workloads. Treat it as a scaling compass, not a stopwatch, and resist micro-optimising code whose n is forever small.
Implementation
Count how work scales with input: a single loop is O(n), a loop inside a loop over the same data is O(n²), halving search spaces is O(log n). Know the amortised costs of library operations (appending to a dynamic array, hash inserts), and when it matters, measure with a profiler to confirm the theory against reality.