Big O for Beginners: How Work Grows as Input Size Increases

What does Big O describe?

Also state which case you are analysing: worst case, average case under assumptions, or another defined situation. The notation alone does not automatically mean worst case.

Compare growth, not machine timings

These are illustrative mathematical growth values, not exact running times for three programs. Constants, implementation details and hardware still influence measured performance.

An algorithm that repeatedly halves a suitable search interval has logarithmic growth in the number of such steps. Scanning every item grows linearly. Comparing every ordered pair of n items can grow quadratically.

Add sequential work and multiply repeated work

Two separate loops that each visit n items perform about 2n visits, which is O(n). A loop of n iterations containing a full n-iteration loop performs n squared visits, which is O(n squared).

Not every visibly nested loop is quadratic. If the inner loop always performs three operations, the total grows linearly. If its length changes with the outer index, count the actual repetitions before simplifying.

Include preparation costs

Binary search on a sorted array uses logarithmically many comparisons, but sorting unsorted data first has its own cost. If you only need one search, the whole workflow may not be better than a linear scan.

For many repeated searches on stable data, preparation can be worthwhile. State the number of queries and the update pattern before comparing designs.

Analyse extra space too

Finding the largest element while storing only the current largest uses constant auxiliary space. Making a full extra copy of n elements uses linear additional space.

Be clear whether you are discussing auxiliary space or including the input itself. Recursive calls may also use call-stack space, even when the function contains few explicit local variables.

A quick exercise

Suppose one method performs 5n operations and another performs n squared operations in a simplified model. At n = 3, their values are 15 and 9. At n = 100, they are 500 and 10,000.

The example shows why asymptotic growth and small-input performance are different questions. Do not turn an O label into a claim that one program is faster for every input.

In Gammal Tech's Algorithms route, use the data-structure knowledge you already have to state which operations are being counted. A good complexity explanation names the input size, the case and the assumptions.