Big-O and Complexity

Why we measure growth, not seconds

Two programs that solve the same problem can both finish instantly on 10 items and still be worlds apart on 10 lakh items. Timing code with a stopwatch tells you about one input on one machine. Big-O notation tells you something more useful: how the amount of work grows as the input grows.

We write the input size as n. If a function looks at every item once, the work grows in step with n, and we say it is O(n) ("order n"). If it compares every item with every other item, the work grows like n × n, so it is O(n²).

Big-O keeps only the part that dominates for large n:

• Constants are dropped: 3n + 5 is just O(n). On huge inputs, the shape of the curve matters far more than the constant in front of it.
• Smaller terms are dropped: n² + n is O(n²), because the n becomes irrelevant next to n².
• It usually describes the worst case, unless stated otherwise.

The common complexities

A rough rule for programming contests and interviews: a computer does about 10⁸ simple steps per second. So with n = 10⁵, an O(n²) solution (10¹⁰ steps) is far too slow, while O(n log n) (about 2 × 10⁶ steps) finishes instantly.

Counting the work

The best way to build intuition is to count. The program below counts the steps three algorithms take as n grows:

• Linear search checks items one by one looking for a value that isn't there, so it checks all n.
• Binary search looks for the same missing value in a sorted array. Each step throws away half of what is left, so it needs about log₂ n steps.
• Every pair compares each item with every later item, which is n(n − 1) / 2 comparisons.

def linear_steps(nums, target):
    steps = 0
    for value in nums:
        steps += 1
        if value == target:
            break
    return steps


def binary_steps(nums, target):
    lo, hi, steps = 0, len(nums) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if nums[mid] == target:
            break
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps


def pair_checks(nums):
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
    return checks


for n in (8, 64, 1024):
    nums = list(range(n))  # sorted: 0, 1, ..., n - 1
    missing = n            # larger than every item, so it is never found
    print(f"n = {n}: linear {linear_steps(nums, missing)}, binary {binary_steps(nums, missing)}, pairs {pair_checks(nums)}")

n = 8: linear 8, binary 4, pairs 28
n = 64: linear 64, binary 7, pairs 2016
n = 1024: linear 1024, binary 11, pairs 523776

When n grows 128 times (from 8 to 1024), linear search does 128 times the work, binary search does fewer than 3 times the work, and the pair check does almost 19,000 times the work. That is what O(n), O(log n) and O(n²) mean in practice.

Reading the complexity of code

You can usually read Big-O straight off the structure of the code:

• A loop over the input is O(n).
• A loop inside a loop, both over the input, is O(n²). Three nested loops is O(n³).
• A loop that halves the problem each time (binary search, or while n > 0: n //= 2) is O(log n).
• Two loops one after the other add up: O(n) + O(n) = O(n).
• Calling a function inside a loop multiplies: n calls of an O(log n) function is O(n log n).
• Built-in operations aren't free. x in my_list in Python, arr.includes(x) in JavaScript and list.contains(x) in Java are all O(n) loops in disguise. Inside another loop they quietly make your code O(n²).

Space complexity

Big-O also describes memory. A function that builds a new array the same size as its input uses O(n) extra space. One that only keeps a few variables uses O(1) extra space. Recursion uses space too: each pending call sits on the call stack, so a recursion that goes n levels deep uses O(n) space.

Many problems are a trade-off between the two. The Two Sum problem in the lab is the classic example: checking every pair uses O(1) space but O(n²) time, while a hash map spends O(n) space to get down to O(n) time.

Best, average and worst case

Linear search finds the first item in one step (best case) but needs n steps when the item is last or missing (worst case). Big-O is normally quoted for the worst case, because that is the guarantee you can rely on. Some structures are quoted by their average or amortised cost instead: a hash map lookup is O(1) on average, and appending to a dynamic array is O(1) amortised, even though an individual operation can occasionally be slower. The arrays and hash maps guides explain why.

Common mistakes

• Counting lines instead of loops. One line like sorted(nums) is O(n log n), not O(1).
• Keeping constants. O(2n) is just O(n). The constant matters for real speed, not for Big-O.
• Forgetting hidden loops in built-in methods such as in, indexOf, contains, slicing and string concatenation in a loop.
• Mixing up different inputs. Looping over a list of size n inside a loop over a list of size m is O(n × m), not O(n²).

Where to go next

Big-O is the language every other guide uses. Continue with Arrays to see why reading arr[i] is O(1) while inserting at the front is O(n), and then Hash maps to see how a clever layout turns an O(n) search into O(1).