Big O Notation Explained Through Small Examples

By Hourly DSA · September 16, 2026 · 4 min read

Big O notation describes an upper bound on how an algorithm's work or memory grows as its input grows. It helps you compare approaches without pretending to predict an exact number of milliseconds.

Start by naming the input size. If you're scanning an array, n usually means its length. If you're comparing two arrays, you might need n and m. A complexity claim becomes much easier to assess once those quantities are clear.

Count repeated work before choosing a label

Imagine checking every value in an array:

for each value in values:
    check(value)

If check takes constant time, doubling the array roughly doubles the number of checks. The total work is linear: O(n).

Now consider reading only the first value from an array that supports constant-time indexing. The amount of work doesn't grow with the array's length. That's O(1), even if the array itself is enormous.

The question is what the algorithm does with the input, not how large the input happens to be today.

Why constants disappear

Suppose you scan an array twice. You do about 2n units of work, which is still O(n). Doubling n still doubles that work.

Similarly, an algorithm doing n² + n operations is O(n²). As n grows, the quadratic term dominates the linear term.

This doesn't mean constants never matter in real programs. Two linear algorithms can have different running times. Big O is a way to discuss growth; measuring performance answers a different question.

Common growth rates you can recognize

Work pattern	Typical tight growth bound
Read a fixed number of array entries	O(1)
Repeatedly halve the remaining search range	O(log n)
Visit each item once	O(n)
Perform logarithmic work for each of n items	O(n log n)
Compare every pair of n items	O(n²)

These are starting points, not rules you can apply without reading the algorithm. For example, a lookup inside a loop may be cheap in one data structure and expensive in another.

In interviews, people often say “the Big O” when they mean the tightest useful bound. Technically, O(n²) is also an upper bound on linear work, but O(n) communicates its growth more precisely.

Two loops don't always mean O(n²)

Two separate scans add together:

for each value in first:
    inspect(value)
for each value in second:
    inspect(value)

If the arrays have lengths n and m, the total is O(n + m), assuming constant-time inspection.

A nested loop that visits every item of the second array for every item of the first is O(nm). It becomes O(n²) when both lengths are n.

But nesting alone isn't proof. In a sliding-window algorithm, an inner loop might advance a left pointer that never moves backward. If each pointer advances at most n times across the entire run, the total pointer movement is O(n), even though one loop sits inside another.

Count how often the work happens overall.

Why halving gives O(log n)

Start with 32 candidates. Halving the range leaves:

32 → 16 → 8 → 4 → 2 → 1

That's five halvings. Starting with 64 requires just one more. A much larger input adds relatively few steps because each step removes a fixed fraction of the candidates.

That's the idea behind binary search. The bound assumes the work done at each step is constant; copying the remaining range at every step would change the analysis.

Count extra space separately

An algorithm can take O(n) time and O(1) extra space. Scanning an array while keeping only a running maximum is one example.

Building a set containing up to n values takes O(n) extra space. Recursive calls also occupy memory: a chain of n active calls uses O(n) stack space, even if you never allocate a visible array.

Be clear about whether you're discussing auxiliary space, which excludes the input and usually the returned output, or total storage. If you must return n items, the output itself needs O(n) space.

A quick check

You scan an array once, keeping a set of previously seen values to detect a duplicate. What are the expected time and worst-case extra-space bounds?

Expected O(n) time and O(n) extra space, assuming expected constant-time hash-set operations. With all distinct values, the set can grow to contain the whole array.

Notice the word “expected.” Hash-table performance depends on the implementation and collision behavior; calling every operation unconditionally O(1) hides an assumption.

Hourly DSA gives you short opportunities to practice these judgments. Before checking an answer, name what grows, count the repeated work, and state the assumption that makes your bound hold.