Published on 22 August 2026 · Updated on 31 August 2026 · 15 min read

Big O notation explained

The doors of a concert hall are about to open. At the check-in desk, a member of staff has a list of guests on a tablet. When Noor arrives, the staff member has to find her name before letting her through. That is easy enough when the list contains a few hundred people, and on a modern tablet almost any sensible search will appear to finish at once. But the same method may also be used by the ticketing company behind the event, where the list is no longer a few hundred names but millions of customer records. Checking them one by one now looks rather less harmless.

We could time the search, but a result such as twelve milliseconds tells us surprisingly little on its own. A faster computer might finish sooner, another programming language might add overhead, and a lucky search might find Noor at the top of the list. More importantly, that single measurement does not tell us what will happen when the list becomes ten or a thousand times larger. Big O notation gives us a way to talk about that growth. It deliberately ignores exact timings and much of the machinery underneath the programme, then asks how the required work or memory changes as the input grows. That makes Big O useful for comparing algorithms, but it also means that it is not a stopwatch: O(n) describes a growth pattern, not a duration of n milliseconds.

From a guest list to O(n)

Start with eight unsorted names stored in an array. You can picture the array as a row of eight numbered slots in memory, with one name in each slot. Because the names are not sorted, the programme has no clue where Noor might be. It reads the first slot, compares that name with Noor, and moves one slot to the right if the names do not match. It keeps doing this until it finds her or reaches the end.

Suppose Noor occupies the eighth slot. The programme reads all eight slots. If the list grows to sixteen names and Noor is last again, it reads sixteen. Doubling the list has doubled the work, and doubling it again would double the work again. This is linear growth, commonly written as O(n). The letter n represents the input size, which in this example is the number of names. In another analysis it might mean the number of pixels in an image or the number of characters in a document. It has no meaning until we define it.

We also need to say what counts as work. For this search, reading and comparing one name is a useful unit. Choosing such a unit is called choosing a cost model. It lets us concentrate on the work introduced by the algorithm without pretending that processor speed, caching, and implementation quality do not exist. We leave those details out of this particular model and return to them when we measure the real programme. The input matters as well: if Noor is in the first slot, the search finishes after one comparison, however long the list is. Linear search therefore has a constant best case and a linear worst case. Big O itself does not mean “worst case”; it can describe either case, so a useful analysis names the case it is discussing.

What happens when the input doubles?

One of the easiest ways to get a feel for these patterns is to double the input and watch what happens to the work. The table is worth reading as a set of behaviours rather than a ranking to memorise.

The names can be misleading if read too literally. O(1) does not mean one instruction or an instant result; a fixed thousand instructions are still constant when that number does not grow with n. The difference only becomes obvious as the input expands. At 1,024 names, a full scan may read 1,024 slots, while a process that repeatedly halves the remaining range needs about ten halvings. A quadratic process at the same input size can perform more than one million units of work. This is the sort of difference Big O helps us notice before a design reaches production.

The middle rows deserve a little more explanation. Work described as O(n log n) usually combines two patterns: the programme handles all n values and does so across a number of levels that grows like log n. Many efficient sorting algorithms have this shape because they repeatedly divide a list and then process the values at each level. Quadratic work often comes from considering pairs. If every guest must be compared with every other guest, doubling the guest list gives each of twice as many guests twice as many possible comparisons, which is why the work grows by about four times rather than two.

Exponential growth is more severe again. Imagine a planning tool that must try every possible group that can be made from the guests. Each new guest can either be included or excluded, so adding that one person doubles the number of groups to inspect. With ten guests there are 1,024 possible groups; with twenty there are 1,048,576. Faster hardware can postpone the problem, but it cannot make repeated doubling gentle.

Finding Noor by discarding half the list

We can search differently if the names are sorted. Instead of starting on the left, read a slot near the middle. If its name comes before Noor, every name to its left can be discarded; if it comes after Noor, every name to its right can be discarded. The names do not move in memory. The programme merely changes the two positions that mark the remaining search area, then repeats the same step inside that smaller area.

Take eight sorted slots containing Adam, Bo, Chen, Dina, Liu, Noor, Omar, and Zoe. The search first reads Dina near the middle. Noor comes later in the alphabet, so the first four slots no longer matter. It then reads Noor and stops after two comparisons. In the least favourable search, a conventional binary search checks at most four relevant slots for eight names and five for sixteen. Doubling the list adds one check instead of doubling the work. This is logarithmic growth, written as O(log n). We omit the logarithm’s base because changing it adds only a fixed multiplier; binary search naturally uses base two because it halves the range.

The word “logarithmic” can sound more forbidding than the idea behind it. It asks how many times a value can be divided by a fixed amount before only one remains. A range of 1,024 slots can be halved ten times because 1,024 is two multiplied by itself ten times. A range of about one million slots takes only about twenty halvings. The input has grown by nearly a thousand times, yet the search has gained only ten steps. That slow growth is what O(log n) captures.

Binary search is not free. The list must already be sorted, it must support direct access to a chosen position, and sorting costs time. If the list changes often or is searched only once, sorting it first may cost more than a direct scan. If it is sorted once and searched thousands of times, the setup cost can be spread across those searches and become a sensible investment. Complexity belongs to a particular operation in a particular situation; saying “binary search is faster” without mentioning the sorted input leaves out the condition that makes it possible.

How does Big O look in code?

This pseudocode writes operators as words. Its comments follow what happens in memory.

(define findNameLinearly (function names targetName)
  ; Memory contains the complete array and one current position.
  (define currentPosition 0)

  (while (lessThan currentPosition (length names))
    ; Read one array slot into a temporary value.
    (define currentName (read names currentPosition))

    (if (equals currentName targetName)
      (return currentPosition))

    ; The array stays unchanged. Only the position moves right.
    (set currentPosition (add currentPosition 1)))

  (return notFound)))

Follow the memory during a search for Noor in the eighth slot. At the start, currentPosition contains zero. The programme reads the name at slot zero into currentName, compares it, and replaces the position with one. The temporary name is overwritten on the next pass; the function does not build a second list of everything it has seen. In the worst case it repeats this process for every slot, so its time grows as O(n). Its extra memory stays O(1) because the position and temporary name occupy a fixed amount of storage no matter how many names the input contains.

Binary search keeps two boundaries around the part of the array that may still contain the name.

(define findNameInSortedList (function sortedNames targetName)
  ; Memory contains the array and two boundary positions.
  (define firstPossiblePosition 0)
  (define lastPossiblePosition (subtract (length sortedNames) 1))

  (while (lessThanOrEqual firstPossiblePosition lastPossiblePosition)
    (define middlePosition
      (floor (divide
        (add firstPossiblePosition lastPossiblePosition)
        2)))

    ; Read the middle slot. The array itself does not move.
    (define middleName (read sortedNames middlePosition))

    (if (equals middleName targetName)
      (return middlePosition))

    (if (comesBefore middleName targetName)
      ; Forget the left half by moving the lower boundary.
      (set firstPossiblePosition (add middlePosition 1))
      ; Forget the right half by moving the upper boundary.
      (set lastPossiblePosition (subtract middlePosition 1))))

  (return notFound)))

Here, firstPossiblePosition and lastPossiblePosition do not hold parts of the list. They hold two numbers that point into the original array. After reading the middle name, the function changes one of those numbers so that half the slots fall outside the remaining range. Nothing is copied or deleted. When the lower boundary passes the upper one, there are no possible slots left and the name is absent. Each pass removes about half the candidates, which gives O(log n) worst-case time, while the three position values keep the extra memory at O(1).

This is also a useful warning about reading code by its shape alone. The binary search contains a loop, but that does not make it O(n); its boundary does not advance one slot at a time. Conversely, two nested loops are not automatically O(n²). Their complexity depends on how often they run and whether both limits grow with the input. Count what the code does rather than matching it to a visual pattern.

Why constants and smaller terms disappear

Suppose our model counts 3n + 5 operations. The three may represent three actions performed for every name, while the five may be setup and cleanup that happen once. If the input grows from 100 to 200 names, the changing part grows from 300 to 600 operations, while the fixed five stays five. At 100 names that fixed work is already a small part of the total; at one million it is barely visible. Big O groups the whole expression with linear functions because the term containing n controls how the cost grows.

We can make that claim concrete without relying on a vague instruction to “drop constants.” For every n of at least one, 3n + 5 is no more than 8n, because the five can be replaced by 5n as an upper bound. A fixed multiple of n therefore stays above the complete cost. The exact choice of eight is unimportant; what matters is that it is fixed and does not grow with the input.

The same reasoning removes smaller terms. In n² + 4n + 20, the square eventually controls the growth. For any n of at least one, the linear term is no more than 4n² and the constant is no more than 20n², so the full expression stays below 25n². We therefore describe it as O(n²). This simplification is about classifying growth, not about claiming that constants have no practical effect. A linear algorithm that performs a thousand expensive operations for every item can lose to a small quadratic loop. Big O tells us which cost is likely to dominate as inputs grow; benchmarks tell us whether the crossover matters for the inputs our users actually have.

Time and memory are separate

Big O can describe any resource that grows, although time and memory are the ones programmers discuss most often. Suppose we want to detect duplicate guest identifiers. Comparing every identifier with every other identifier takes quadratic time and little extra memory. Keeping the identifiers in a set can often reduce the expected time to linear, but that set stores up to n extra entries. The faster approach has expected O(n) time and O(n) extra space, so we have bought speed with memory.

Space figures need the same care as time figures. The input list already occupies memory, and auxiliary space means the memory the algorithm needs in addition to that input. Recursive functions may also consume memory through their call stack, even when they never create an explicit array. Calling an algorithm simply “O(n)” without saying whether that refers to its time or its space leaves half the analysis unstated.

Upper bounds and different cases

Formally, Big O gives an eventual upper bound. A cost T(n) is in O(g(n)) if we can choose a fixed multiplier and a starting input size after which that multiple of g(n) always stays at or above the cost. The starting point matters because Big O describes what happens as inputs grow, not necessarily what happens for the first few values. The multiplier must remain fixed; choosing a larger multiplier for every new n would explain nothing.

This definition has a slightly odd consequence. A linear function is technically also in O(n²), O(n³), and many larger classes because all of those ceilings eventually stay above it. Saying that linear search is O(n²) is therefore true in the formal sense, but it throws away the most useful information we have. In practice we normally give the smallest simple upper bound we can justify.

Big Theta, written as Θ, lets us say that a growth rate is tight. The function is bounded both above and below by fixed multiples of the same shape, so it cannot secretly grow much more slowly. Linear search’s worst case is Θ(n) because it performs work proportional to the number of names, while its best case is Θ(1) because finding Noor in the first slot always takes a fixed amount of work. Everyday software discussions often use “Big O” for this tightest simple class. The shorthand is common and usually harmless, provided we remember what the formal notation actually promises.

Average and amortised costs answer other questions. An average search needs explicit assumptions about whether Noor is present and how likely she is to occupy each slot. Without those assumptions, there is no meaningful average to calculate. Amortised analysis does not assume random inputs. It spreads occasional expensive operations across a sequence of operations. Most appends to a dynamic array write into one free slot, but when the array fills up it must reserve a larger memory block and copy its existing values. That single append can cost O(n). If the capacity doubles each time, those costly copies happen less and less often, and a long sequence has O(1) amortised cost per append.

When is Big O useful?

Big O is most useful before growth becomes a production incident. A duplicate check that compares every pair may be perfectly acceptable for twenty records, yet become painful when an import contains a hundred thousand. Writing down the growth rate makes that risk discussable. It can also show why adding an index or a set improves repeated lookups, while making the added memory cost explicit.

Some problems need more than one measure of input. A graph consists of vertices, such as people in a social network, and edges, such as the connections between them. Traversing it is commonly O(V + E) because the programme may need to inspect both. Two graphs can contain the same number of people but radically different numbers of connections, so replacing both variables with n would hide a real source of work. The same principle applies to a grid with separate width and height or an operation that compares two independently growing collections.

Big O still cannot tell us whether code is correct, readable, cache-friendly, or fast enough. It does not include network latency, the cost of allocating memory, parallel work, or the exact point where one implementation overtakes another. Nor does a lower growth class automatically justify a more complicated design when the input has a firm and small limit. Use Big O to understand the direction of growth, then benchmark the implementation with realistic data. The analysis and the measurement answer different questions, and good decisions need both.

Recap and takeaway

Big O describes how work or memory grows with its input. To use it properly, define the input size, choose what you count, and name the case under discussion. Then ask what happens when the input doubles. A full scan does roughly twice the work, a halving search adds about one step, and an every-pair comparison does roughly four times the work.

If only one idea sticks, let it be this: Big O is a growth model, not a speed rating. It removes enough detail to let us reason about scale, but those omitted details do not disappear from the running programme. Constants, hardware, setup work, and the input sizes users actually provide still determine which implementation wins.

Further reading

• Wikipedia: Binary search algorithm
• Wikipedia: Sorting algorithm
• Wikipedia: Hash table
• Wikipedia: Amortized analysis