Big-O Notation Explained: Time & Space Complexity from Scratch

In plain words — the crowd analogy

Imagine you're looking for a friend in a crowd. If you know exactly where they're standing (seat A7), you walk straight there — one step, regardless of how big the crowd is. That's O(1). If the crowd is sorted by height and you can split it in half each time ('my friend is taller than this half'), you narrow it down in about log₂(crowd size) splits — O(log n). If you have to walk every row scanning faces, you do work proportional to the crowd size — O(n). And if you have to check every person against every other person for some reason, that's crowd × crowd — O(n²). Big-O is just a formal name for which of those shapes your algorithm follows.

The problem Big-O solves

Suppose two programs both find a name in a list of contacts. Timed on your machine, program A takes 2 ms and program B takes 5 ms. Is A better? You can't tell — maybe A was tested on 100 contacts and B on 100,000. Maybe A is faster on small lists but falls apart on big ones. Raw timings conflate the algorithm with the machine, the language, and the test data. What we want is a measure of the algorithm itself: how does its work grow as the input grows?

Big-O answers exactly that. We count the basic operations an algorithm performs as a function of the input size n, then keep only the fastest-growing term and drop constant factors. If an algorithm does 3n² + 10n + 50 operations, we say it is O(n²) — because once n is large, the n² term utterly dominates, and whether it's 3n² or 5n² is a hardware-level detail, not an algorithmic one.

The complexity classes you'll actually meet

Growth curves — steps required vs. input size n

Steps
  |
1T|                                              O(n²) ↗
  |                                         ↗
  |                                    ↗
1B|                               ↗
  |                          ↗
  |                 O(n) ↗
1M|           ↗
  |      ↗
  |  ↗               O(n log n) (just above O(n), not shown separately)
1K| ↗
  |____O(log n) (nearly flat)
  |__O(1) (truly flat)
  +─────────────────────────────────────────► n
    1    10   100   1K   10K  100K   1M

At n = 1,000: O(1)=1, O(log n)=10, O(n)=1K, O(n²)=1,000,000
At n = 1,000,000: O(log n)≈20, O(n)=1M, O(n²)=10¹²

How to analyze code, step by step

Complexity analysis is mechanical once you know the rules. Here they are, in the order you apply them:

1. Simple statements are O(1). Arithmetic, assignments, comparisons, reading an array element by index — constant time each.
2. Sequential blocks add. O(n) work followed by O(n²) work is O(n + n²) = O(n²): keep only the dominant term.
3. Loops multiply. A loop running n times over O(1) work is O(n). A loop over a loop, both n iterations, is O(n · n) = O(n²).
4. Watch what the loop variable does. A loop that doubles i each time (i = 1, 2, 4, 8, …) runs log₂ n times → O(log n). Halving is the same. Loops that grow by adding are linear; loops that grow by multiplying are logarithmic.
5. Different inputs get different variables. A loop over array A (length n) inside a loop over array B (length m) is O(n·m), not O(n²). Never collapse distinct inputs into one variable.
6. For recursion, count calls × work per call. A function that makes one recursive call on half the input with O(1) extra work is O(log n) (binary search). Two calls on halves with O(n) merge work is O(n log n) (merge sort). Two calls on n−1 is O(2ⁿ) (naive Fibonacci). The recursion lesson develops this fully.
7. Beware hidden loops. Library calls have costs: slicing an array copies it (O(n)), string concatenation in a loop is often O(n²) total, 'contains' on a list is O(n). Big-O analysis includes the work your libraries do for you.

Worked examples

Example 1: analyzing a compound function

Consider a function that, for an array of n numbers, first finds the maximum (one pass), then for each element counts how many other elements are smaller (a pass inside a pass), then does a binary search over a sorted copy. The pieces: the max pass is O(n); the count-smaller phase is a loop of n iterations each doing O(n) work → O(n²); sorting the copy is O(n log n); the binary search is O(log n). Total: O(n) + O(n²) + O(n log n) + O(log n). The dominant term is n², so the function is O(n²) — and now you also know exactly which phase to attack to speed it up.

Example 2: the deceptive nested loop

function countPairs(arr):
    count = 0
    for i from 0 to n-1:        # outer loop: n iterations
        for j from i+1 to n-1:  # inner loop: n-i-1 iterations
            if arr[i] + arr[j] == target:
                count += 1
    return count

Even though the inner loop doesn't always run n times, the total work summed across all outer iterations is n(n-1)/2 — which is O(n²). This is the classic two-nested-loops pattern: if both loops range over the input size independently or semi-dependently, the result is quadratic.

Example 3: the logarithmic loop

function logLoop(n):
    i = 1
    while i < n:
        doSomething()   # O(1) work
        i = i * 2      # i: 1, 2, 4, 8, 16, …, n

# How many iterations?
# i doubles each time, so we need k such that 2^k >= n
# k = log₂(n) iterations → O(log n)

Space complexity

The same notation measures memory. Space complexity counts the extra memory an algorithm allocates beyond its input (this is sometimes called auxiliary space). An in-place algorithm that uses a few counters is O(1) space regardless of input size. Building a copy of the input is O(n) space. A recursive function uses stack space proportional to its maximum call depth — so even 'no allocations' recursion over n items can cost O(n) space, a fact that surprises many beginners and crashes real programs with stack overflows.

Time and space often trade against each other. Hash tables spend memory to make lookup O(1); dynamic programming spends memory on a table of saved answers to collapse exponential time to polynomial. 'Can I spend memory to save time here?' is one of the most productive questions in algorithm design.

Best, average, worst — and amortized

A single algorithm can have different complexities depending on the input it receives. Linear search finds its target on the first element in the best case (O(1)), halfway through on average (O(n/2) = O(n)), and at the end or not at all in the worst case (O(n)). Convention: when someone states one number, it's the worst case unless they say otherwise — worst case is the promise you can build systems on. Average case matters when the worst case is rare and you understand the input distribution (quicksort is the classic example: O(n log n) average, O(n²) worst, and the average is what you see in practice with randomized pivots).

Amortized complexity is subtler and worth getting right, because it explains dynamic arrays (next lesson). Some operations are cheap almost always but occasionally expensive. Appending to a dynamic array is O(1) — until the array is full, at which point it allocates double the capacity and copies all n elements, an O(n) event. But that expensive event happens so rarely (only after n cheap appends) that the total cost of n appends is still O(n), i.e., O(1) amortized per append. Amortized analysis averages cost over a worst-case *sequence* of operations — it's a guarantee about totals, not a probabilistic claim.

Amortized O(1) append — the doubling argument

Capacity: 1  2  4  8  16  …  n
Copy cost: 1  2  4  8  16  …  n   (on each resize)

Appends:   1  2  3  4   5  …  n   (each is "free" until resize)

Total copy work for n appends:
  = 1 + 2 + 4 + 8 + … + n
  = 2n - 1   (geometric series)
  = O(n)

Cost per append = O(n) / n = O(1) amortized ✓

Compare: grow by +1 each time (additive):
  Copy costs: 1 + 2 + 3 + … + n = n(n+1)/2 = O(n²)
  Cost per append = O(n) — quadratic total. Never do this.

Common pitfalls

• Believing Big-O predicts real speed at small n. It doesn't — constants matter for small inputs. Insertion sort (O(n²)) beats merge sort on 20 elements, which is exactly why production sorts switch to it for tiny subarrays.
• Dropping the wrong variable. O(n + m) does not simplify to O(n). If the two inputs vary independently, both stay in the answer.
• Calling nested loops O(n²) reflexively. A nested loop where the inner index continues from the outer one (the classic two-pointer pattern) can be O(n) total. Count total operations, not loop keywords.
• Forgetting the cost of built-ins. Concatenating strings in a loop, slicing arrays, or checking membership in a list all hide O(n) work per call.
• Confusing amortized with average. Amortized is a worst-case guarantee over a sequence of operations; average-case is an expectation over input distributions. Hash tables are 'O(1) average'; dynamic-array append is 'O(1) amortized'. Different claims.
• Ignoring space complexity. An algorithm that uses O(n²) extra memory for a hash table may be impractical even if its time complexity is fine. Always state both.

Practice problems

1. Classify each snippet. For each: (a) a single for-loop over n items; (b) two sequential for-loops over n items; (c) a for-loop over n with an inner while that halves a variable each iteration; (d) a recursive function that calls itself twice with n/2 each time and does O(n) work at each level — state the time complexity and justify it.
2. Spot the hidden O(n²). Take any string-building loop in a language where strings are immutable (Java, Python, etc.) and explain why it's O(n²). Then rewrite it with a builder and explain why the rewrite is O(n).
3. Amortized reasoning. A stack supports push (O(1)) and popAll (empties the stack, costing O(k) where k is current size). Argue that a sequence of n pushes and one popAll costs O(n) total, i.e., O(1) amortized per operation.

Key takeaways

• Big-O measures growth rate of work versus input size, ignoring constants and hardware — it's the machine-independent language of efficiency.
• Memorize the ladder: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!). The gaps between rungs decide what's feasible.
• Analysis is mechanical: statements are O(1), sequences add (keep the dominant term), loops multiply, halving loops are O(log n), recursion is calls × work per call.
• Space complexity uses the same notation; recursion depth counts as space.
• Worst case is the default claim; amortized analysis explains why occasional expensive operations (like array resizing) can still be cheap per operation.

With the vocabulary in place, the course turns to the most fundamental structure in computing: arrays and dynamic arrays — where you'll see amortized O(1) append in action. For drilling complexity classes until they're reflexive, the **AI Learning app** has offline quiz decks on exactly this material.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play