Time Complexity and Big O Notation

Time complexity describes how the running time of an algorithm grows as its input gets larger, independent of any specific computer, programming language, or moment in time. Big O notation is the mathematical shorthand for that growth rate: instead of saying an algorithm takes about three milliseconds for a hundred items on a particular laptop, you say it is O(n) — a statement that stays true whether the input has a hundred items or a hundred million. Understanding Big O lets you predict, before you ever run a program, whether an algorithm will scale gracefully or grind to a halt as data grows, and it is the language interviewers, code reviewers, and performance-minded engineers expect you to speak fluently.

Overview: How Big O Notation Works

Picture two ways of finding a name in a stack of business cards. If the cards are in random order, the only option is to flip through them one at a time until you find the name or run out of cards — on average you look at about half the stack, and in the worst case you look at every single card. If the cards are alphabetized, you can open to the middle, decide whether the name comes before or after that point, and discard half the remaining cards with every comparison. The first approach is linear — the work grows in direct proportion to the number of cards. The second is logarithmic — the work grows only as fast as the number of times you can cut the pile in half. Big O notation is simply a formal way of naming that difference: the unsorted search is O(n) and the sorted, halving search is O(log n).

Formally, an algorithm is O(g(n)) if the number of basic operations it performs grows no faster than some constant multiple of g(n), for large enough n. Two details matter enormously in practice. First, constants are dropped: an algorithm that does 3n + 7 operations and one that does 100n operations are both O(n), because what matters is the shape of the growth curve, not the exact count. Second, only the fastest-growing term survives: O(n^2 + n) collapses to O(n^2), because once n is large, the n^2 term dwarfs the n term. Big O also conventionally describes the worst case unless stated otherwise — how the algorithm behaves on the input that is hardest for it, which is the safest assumption to design around.

In practice, you rarely derive Big O from a formal proof — you read the code and reason about it structurally. A few rules of thumb cover most cases you will encounter in this course:

• A single loop that runs n times contributes a factor of n.
• Nested loops multiply: a loop inside a loop, each running n times, is O(n) * O(n) = O(n^2).
• Sequential loops add, and the sum collapses to the largest term: one loop of n followed by another loop of n is O(n) + O(n) = O(2n), which simplifies to O(n) — not O(n^2). This is one of the most common sources of confusion for people new to complexity analysis; see Common Mistakes below.
• Calling a function that has its own cost inside a loop multiplies the costs. Checking item in some_list — itself O(n) — inside a loop that runs n times produces O(n^2) overall, even though no line of code looks like a nested loop.
• Recursive functions are analyzed by how many calls are made and how much work each call does; a function that makes one recursive call per invocation and does O(1) work per call is typically O(n), while one that makes two recursive calls per invocation, like naive Fibonacci, can be O(2^n).

Time and Space Complexity

Time complexity measures operations as a function of input size n. Space complexity measures the extra memory an algorithm needs beyond its input, also as a function of n — sometimes called auxiliary space to make clear the input itself is not being counted. The table below lists the growth classes you will see constantly in this course, from fastest to slowest.

Notation	Name	Typical example
O(1)	Constant	Reading list[i] by index; a dict/set lookup
O(log n)	Logarithmic	Binary search on a sorted array
O(n)	Linear	Scanning a list once
O(n log n)	Linearithmic	Efficient sorting: merge sort, Python’s Timsort
O(n^2)	Quadratic	Comparing every pair; nested loops over the same input
O(2^n)	Exponential	Naive recursive Fibonacci; brute-force subsets

Some algorithms behave differently depending on the input, which is why complexity is often broken into best, average, and worst case. Linear search on a list where the target happens to be the first element is best-case O(1), but its worst case — the target is absent, or sits at the very end — is O(n), and that worst case is normally quoted as the complexity of linear search, since it is the guarantee you can actually rely on. A dict or set lookup is O(1) on average because Python’s hash table implementation spreads keys across buckets, but in the rare worst case where many keys collide into the same bucket, a lookup degrades toward O(n).

Space complexity deserves the same care. An iterative function that keeps a running total uses O(1) extra space no matter how large the input is. A recursive function, by contrast, pushes a new stack frame for every call that has not yet returned, so a recursive sum over n elements uses O(n) auxiliary space even though it looks like it is just adding numbers — the cost hides in the call stack, not in any variable you declared. This also means Python’s default recursion limit, a little over a thousand frames, is a real practical ceiling: a naive recursive solution that is correct on small inputs can crash with a RecursionError on large ones, which is why deeply-recursive problems are often rewritten iteratively.

Examples

Example 1: Constant, Linear, and Quadratic Growth Side by Side

This example defines three small functions, one from each of the most common growth classes, and runs them on the same six-item list so you can see how differently they are structured even though the input is identical.

def get_first(items: list[int]) -> int:
    return items[0]


def sum_all(items: list[int]) -> int:
    total = 0
    for item in items:
        total += item
    return total


def count_pairs(items: list[int]) -> int:
    count = 0
    for i in range(len(items)):
        for j in range(len(items)):
            count += 1
    return count


numbers = [4, 8, 15, 16, 23, 42]
print(get_first(numbers))
print(sum_all(numbers))
print(count_pairs(numbers))

Output:

4
108
36

get_first does exactly one operation regardless of the list’s length, so it is O(1). sum_all touches every element exactly once in a single loop, so it is O(n) — with six items it adds 4 + 8 + 15 + 16 + 23 + 42 to get 108. count_pairs has a loop nested inside another loop, both running the full length of the list, so it performs len(items) * len(items) increments — with six items that is 6 * 6 = 36, matching the printed result. The input never changed size; only the shape of the code changed, and that shape is exactly what Big O captures.

Example 2: Linear Search vs. Binary Search, Counted

Big O is easiest to trust once you see it counted directly instead of asserted. This example instruments both a linear search and a binary search to count how many comparisons each performs while looking for the same target in the same sorted list of fifty even numbers, with the target placed at the very end — the worst case for both algorithms.

def linear_search_count(arr: list[int], target: int) -> tuple[int, int]:
    comparisons = 0
    for index, value in enumerate(arr):
        comparisons += 1
        if value == target:
            return index, comparisons
    return -1, comparisons


def binary_search_count(arr: list[int], target: int) -> tuple[int, int]:
    comparisons = 0
    left, right = 0, len(arr) - 1
    while left <= right:
        comparisons += 1
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid, comparisons
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1, comparisons


sorted_numbers = list(range(0, 100, 2))
target = 98

linear_index, linear_comparisons = linear_search_count(sorted_numbers, target)
binary_index, binary_comparisons = binary_search_count(sorted_numbers, target)

print(f'Linear search found {target} at index {linear_index} using {linear_comparisons} comparisons')
print(f'Binary search found {target} at index {binary_index} using {binary_comparisons} comparisons')

Output:

Linear search found 98 at index 49 using 50 comparisons
Binary search found 98 at index 49 using 6 comparisons

sorted_numbers holds the even numbers from 0 to 98, fifty values in total, with 98 as the last element. linear_search_count has to walk past every element before reaching the last one, so it uses 50 comparisons — one per element, confirming O(n). binary_search_count starts with the whole range and cuts it roughly in half on every iteration: 50 -> 25 -> 12 -> 6 -> 3 -> 1 elements remaining, which is why it only needs 6 comparisons. Doubling the list size would add only one more comparison to the binary search but roughly fifty more comparisons to the linear search — that gap is O(log n) versus O(n) made concrete.

Example 3: Why String Concatenation in a Loop Is O(n^2)

Some hidden costs come from the data structures you choose, not just the loops you write. Python strings are immutable, so every time you write result += word, Python must allocate an entirely new string and copy the old contents into it. Doing that inside a loop of n iterations means the total number of characters copied grows quadratically, even though the code looks perfectly ordinary.

def build_with_concat(words: list[str]) -> str:
    result = ''
    for word in words:
        result += word + ' '
    return result.strip()


def build_with_join(words: list[str]) -> str:
    return ' '.join(words)


words = ['big', 'o', 'notation', 'describes', 'growth', 'rate']
print(build_with_concat(words))
print(build_with_join(words))

Output:

big o notation describes growth rate
big o notation describes growth rate

Both functions print the identical sentence, which is exactly why this trap is dangerous — the output looks correct and the difference is invisible on small inputs like this six-word list. build_with_concat creates a brand-new string object on every iteration, copying everything accumulated so far plus the next word; across n iterations that adds up to roughly 1 + 2 + 3 + ... + n characters copied, which is O(n^2). build_with_join lets Python’s str.join calculate the total length once and copy every piece exactly one time, which is O(n). On six words the difference is unmeasurable; on a hundred thousand words, the concatenation version can be dramatically slower.

How Binary Search Narrows the Search, Step by Step

To see the O(log n) shrinking in action, trace binary search on the sorted array [3, 9, 14, 22, 27, 33, 41, 48] (eight elements, indices 0 through 7) while searching for 33.

Step	left	right	mid	arr[mid]	Action
1	0	7	3	22	22 is less than 33, so search the right half: left becomes 4
2	4	7	5	33	Match found at index 5

Two comparisons were enough to locate the target in an eight-element array, because each comparison eliminates half of the remaining candidates. Doubling the array to sixteen elements would only add one more comparison, to three; doubling again to thirty-two would add a fourth. That halving pattern is precisely what log2(n) measures, and it is why binary search is written O(log n) rather than O(n) like the linear scan that inspects one element at a time.

Common Mistakes

Mistake 1: Trusting List Membership Tests Inside a Loop

It is easy to write a duplicate-finder that looks clean without noticing its complexity has quietly become quadratic:

def find_duplicates_slow(items: list[int]) -> list[int]:
    seen = []
    duplicates = []
    for item in items:
        if item in seen:
            duplicates.append(item)
        else:
            seen.append(item)
    return duplicates


def find_duplicates_fast(items: list[int]) -> list[int]:
    seen = set()
    duplicates = []
    for item in items:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates


numbers = [1, 2, 3, 2, 4, 1, 5]
print(find_duplicates_slow(numbers))
print(find_duplicates_fast(numbers))

Output:

[2, 1]
[2, 1]

Both functions produce the same result, but find_duplicates_slow checks item in seen against a plain list, and membership testing on a list is O(n) because Python has to scan it element by element. Doing that check inside a loop that already runs n times makes the whole function O(n^2). find_duplicates_fast makes one change — seen is a set instead of a list — and membership testing on a set is O(1) on average, because it is backed by a hash table rather than a sequential scan. That single change brings the function down to O(n) overall, with no change in output.

Mistake 2: Confusing Sequential Loops With Nested Loops

A very common analysis error is assuming that any code with two loops must be O(n^2). The structure matters, not the count of loops:

# Two SEQUENTIAL loops -> O(n) + O(n), which simplifies to O(n)
for x in items:
    process(x)
for y in items:
    handle(y)

# Two NESTED loops -> O(n) * O(n) = O(n^2)
for x in items:
    for y in items:
        compare(x, y)

The first pair of loops runs one after another — the second loop only starts once the first has completely finished — so the total work is O(n) + O(n), which simplifies to O(n). The second pair is nested: for every single pass through the outer loop, the inner loop runs all the way through again, so the total work is O(n) * O(n) = O(n^2). When analyzing unfamiliar code, check whether one loop is written inside the body of another, or merely written after it — indentation, not loop count, decides whether the costs add or multiply.

Best Practices

• Always state which variable is growing — usually n for a list or string length, but V and E for graphs — a Big O without a stated variable is meaningless.
• Analyze loops structurally: multiply the complexity of nested loops, add the complexity of sequential ones, and remember that adding two same-order terms still collapses to that order.
• Watch for hidden costs inside a loop body: a call to sorted(), a membership check on a list, or string concatenation can each turn an apparently O(n) loop into O(n log n) or O(n^2).
• Prefer set or dict over list whenever you need repeated membership tests — the difference between O(n) and O(1) per check compounds fast inside a loop.
• Build strings with a list and ''.join(...) instead of repeated += concatenation when the number of pieces is not tiny.
• Quote worst-case complexity by default unless you have a specific reason to discuss the average case, as with hash tables — worst case is the guarantee your code actually has to honor.
• Do not ignore space complexity: a recursive solution that looks elegant can silently cost O(n) stack space, or even hit Python’s recursion limit on large inputs.
• When unsure of an algorithm’s complexity, do what this lesson does — instrument it with a counter and trace it on a small, deterministic input by hand before trusting your intuition.

Practice Exercises

1. Write a function find_max(items: list[int]) -> int that returns the largest value in a list using a single loop. State its time and space complexity, and explain why it cannot do better than that time complexity on an unsorted list.
2. A function loops over a list of n items, and inside the loop body it calls sorted() on a separate, fixed-size list of 10 items each time. What is the overall time complexity of the function, in terms of n? (Hint: a fixed-size operation contributes a constant, not a variable, factor.)
3. Classify the time complexity, in terms of n, of this pattern: for i in range(n): for j in range(i): do_something(). (Hint: sum the length of the inner loop across every value of i from 0 to n - 1, and compare the result to the O(n^2) class covered in this lesson.)

Summary

• Big O notation describes how an algorithm’s resource use grows with input size n, ignoring constants and lower-order terms.
• Common classes from fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).
• Nested loops multiply complexity; sequential loops add, and the sum collapses to the largest term.
• Hidden costs — list membership tests, string concatenation, calls to library functions — can silently turn a linear-looking loop into a quadratic one.
• Big O by convention describes the worst case unless the average case is explicitly called out, as with hash-based dict/set lookups (O(1) average, O(n) worst case).
• Space complexity counts extra memory, including recursion’s call stack — a recursive function can be O(n) in space even if it looks like it uses no extra variables.
• When in doubt, count actual operations on a small, concrete input rather than guessing.