Home

---

3. Writing efficient algorithms

The performance of an algorithm is not fixed; it often changes dramatically as the size of the input grows. An approach that feels instantaneous on 1,000 items can become unusable on 100,000—and catastrophically slow on 100 million—because the number of operations may grow faster than the data itself. This is why performance analysis must consider not only “how fast is it today,” but “how does it scale as the problem gets larger.”

In computer science, this is precisely the purpose of asymptotic notation, most notably Big O notation. Big O provides a disciplined way to describe the growth rate of an algorithm’s running time (or memory usage) as input size, n, increases. Rather than focusing on exact milliseconds—which vary by hardware, compiler, and environment—Big O focuses on the dominant factor that drives growth, allowing you to reason about performance at scale.

Why Big O matters: the scalability lens

Big O is fundamentally a tool for evaluating scalability:

• It approximates how the number of basic operations increases as the input size increases.

• It helps compare alternative algorithms independent of implementation details.

• It highlights whether a solution will remain feasible as data volumes grow.

This is especially critical when data sizes move beyond “desktop scale.” Consider what happens when your algorithm must handle:

• 100,000 elements: many inefficient approaches still “work,” but delays become noticeable.

• 100 million elements: algorithms with poor scaling can become practically impossible.

• 10 billion elements: only highly efficient approaches are viable, often requiring additional architectural strategies (parallelism, streaming, indexing, distributed processing).

Intuition through common growth rates

Big O categories correspond to familiar scaling behaviors:

• O(1) (constant): time does not grow with n (e.g., array indexing).

• O(log n) (logarithmic): grows very slowly (e.g., binary search).

• O(n) (linear): doubles when n doubles (single pass through data).

• O(n log n): typical of efficient sorting and many divide-and-conquer approaches.

• O(n²) (quadratic): grows rapidly (nested loops over the same dataset).

• O(2ⁿ) or O(n!): explodes so quickly it becomes unusable even for modest n.

This matters because small differences in growth rate become enormous at large n. An O(n²) approach may be acceptable at 10,000 elements, borderline at 100,000, and completely infeasible at 10 million. Conversely, an O(n log n) or O(n) solution may scale comfortably.

What Big O does (and does not) measure

Big O does not usually count every instruction in your code. Instead, it captures the dominant term that drives growth, ignoring constants and lower-order terms. For example:

• 3n + 200 is still O(n) because as n grows, the 200 becomes irrelevant.

• n² + n is O(n²) because n² dominates at scale.

This abstraction is a strength: it lets you make robust decisions early, even before precise benchmarking is possible.

Why this is essential in “big data” and high-volume systems

When working with large datasets—whether in databases, risk engines, ETL pipelines, Excel/VBA processes, or distributed systems—Big O is indispensable. It helps you anticipate failure modes before they occur:

• A naive nested loop over records (O(n²)) can turn a 2-second job into a 6-hour job as volume grows.

• Repeatedly searching an unsorted list (O(n) per lookup) inside a loop can quietly become a bottleneck; switching to a hash-based lookup can reduce it to ~O(1) average per lookup.

• Sorting repeatedly inside a loop can push the runtime from O(n log n) to something far worse.

In such environments, writing code “that works” without understanding Big O can be risky. The code may pass tests and appear performant in development, yet fail in production when volumes increase. In the worst case, the impact is not just slow execution but operational disruption: missed batch windows, timeouts, runaway costs, and user-facing instability.

Practical takeaway

Big O notation provides a scalable mental model: it helps you estimate how an algorithm behaves as data grows, choose safer designs upfront, and avoid performance disasters that only reveal themselves at high volumes. Benchmarking tells you what is fast today on a specific machine; Big O tells you what will still be fast tomorrow when the dataset is 100× larger.

---

Home