Counting steps and Big-O

Why this matters

Two programs can give the same answer and still be very different products. One answers in a blink. The other makes the user wait a minute, or freezes the machine when the data gets large. The difference is rarely a faster computer. It is almost always the way the work is organised.

Complexity analysis is the skill of predicting that difference before you run anything. It lets you look at ten lines of code and say "this will be fine for a thousand items and hopeless for a million". Interviewers ask about it in nearly every coding round. Real teams use it when a page gets slow, when a nightly job stops finishing, or when a bill for cloud servers doubles.

This lesson builds the idea from the ground. You will count steps in small programs, see why exact counts are not what matters, learn the notation that throws away the unimportant parts, and practise reading code the way an engineer does.

Two programs, one answer

Suppose you are asked: what is the sum of the numbers from 1 to n? Here are two ways to answer.

55
55
500500
500500

Both functions agree. But think about what each one does when n is a billion. sum_loop adds a billion numbers one at a time. sum_formula does one multiplication, one addition and one division, whatever n is. The first one's work grows with n. The second one's work stays the same.

That is the whole subject in miniature. We do not ask "how many seconds did it take?". We ask "how does the amount of work change when the input gets bigger?".

An everyday picture helps. Imagine you cook for guests. Boiling one pot of rice takes about 20 minutes whether you cook for 2 people or 6, because the pot is big enough. That is work that does not grow with the number of guests. Peeling potatoes is different: 10 guests need about five times the peeling that 2 guests need. That work grows in step with the guest count. And greeting everyone is worse: if every guest must shake hands with every other guest, 10 guests make 45 handshakes and 100 guests make 4,950. The work grows much faster than the crowd. Complexity analysis is the habit of asking, for each part of a program, which of these three kinds it is.

Why a stopwatch is not enough

You could time a program with a clock. People do, and it has its place, but it cannot answer the question above, for four reasons.

1. The machine matters. The same code runs faster on a new laptop than on an old phone. A time in seconds describes the machine as much as the code.
2. The input matters. A program may be quick on the three items you tried and slow on the three million your users have.
3. The language and settings matter. Python, Java and C++ run the same idea at very different speeds. A debug build is slower than a release build.
4. The noise matters. Other programs on your computer, power saving and caches change timings from one run to the next.

What we want is a measure that belongs to the algorithm itself: a recipe for solving a problem. An algorithm is a finite list of steps that solves a problem. The measure should say how the number of steps grows as the input grows, and it should not care about the machine.

That measure is called time complexity. Its companion, space complexity, counts extra memory instead of steps. We start with time.

What counts as one step

To count steps we need an agreement on what a step is. We use a simple model. These count as one step each:

• an arithmetic operation such as a + b or a * b
• a comparison such as a < b or a == b
• an assignment such as x = 5
• reading or writing one element of a list by its position, such as nums[3]
• returning a value or calling a function (not counting the work inside the function)

Real processors differ. An addition is faster than a division. Reading from memory that is far away is slower than reading from memory that is close. We ignore all of that on purpose. The model says: every basic operation costs the same fixed amount of time, a constant. A constant here means a number that does not depend on the input size.

This looks like a crude simplification, and it is. It works because of what we do next. We will care about how the count grows, not the count itself, and a constant factor like "a division costs three times an addition" does not change how fast something grows.

The input size, written n, is the number that measures how big the input is. For a list it is the number of items. For a string it is the number of characters. For a single number such as "is this number prime?" the size is a little subtler, which we cover later in this lesson. Always say what n is before you count. Many wrong answers come from not saying it.

Counting the steps of a real function

Let us count precisely for sum_loop. Here it is again with each line numbered in a comment.

def sum_loop(n):
    total = 0                    # line A
    for i in range(1, n + 1):    # line B
        total += i               # line C
    return total                 # line D

• Line A runs once: 1 step.
• Line B is the loop header. It sets i to a new value each time around, n times. Roughly n steps. (The loop also does a final check that finds the loop is finished. We count that as 1 more.)
• Line C runs once per pass: n times, and each time it does one addition and one assignment. Call that 2 steps per pass, so 2n.
• Line D runs once: 1 step.

Adding up: 1 + (n + 1) + 2n + 1 = 3n + 3.

So the function takes about 3n + 3 steps. For n = 10 that is 33 steps. For n = 1,000 it is 3,003 steps. For n = one million it is 3,000,003 steps.

You will notice something. Whether we say 2n or 3n or 5n for the loop body, and whether the extra bit at the end is 1 or 3 or 10, the answer is "something close to a constant times n". Counting every detail did not buy us anything. Another engineer who counts line C as a single step gets 2n + 3 instead, and the conclusion is the same.

We can ask the computer to count for us. Below, the function carries a counter that goes up by one for each model step. Run it and compare with the formula 3n + 3.

0 3 3
1 6 6
10 33 33
100 303 303
1000 3003 3003

The column of steps matches 3n + 3 every time. Notice what happens when n is 0: the loop never runs, and we still spend 3 steps. That fixed cost is why the formula has a "+ 3".

Now look at the pattern. If you multiply n by 10, the step count roughly multiplies by 10 as well: 303 to 3003. That is the signature of work that grows in a straight line with the input.

Throwing away what does not matter

Big-O notation is a formal way of saying "the part that dominates". We follow two rules.

Rule 1: drop lower-order terms. When n is large, the biggest term swallows the others. Take n^2 + 100n + 5000. At n = 10 the pieces are 100, 1,000 and 5,000, so the constant wins. At n = 1,000 they are 1,000,000, 100,000 and 5,000, so n^2 wins by a mile. At n = 1,000,000 the n^2 part is 10^12 and the other parts are rounding errors.

Rule 2: drop constant multipliers. 3n and 50n both grow in a straight line. If you double n, both double. Their lines differ only in steepness. The constants depend on the machine, the language and how we chose to count, which are the things we decided not to care about.

Apply both rules to 3n + 3: drop the + 3, drop the 3, keep n. We say the function is O(n), read "big-O of n" or "order n".

Run the next program to see how little the small terms matter once n grows. It prints what share of 7n^2 + 50n + 300 comes from the n^2 part.

n           7n^2 + 50n + 300   share from 7n^2
1           357                1.96%
10          1500               46.67%
100         75300              92.96%
1000        7050300            99.29%
100000      70005000300        99.99%

At n = 1 the quadratic part is under 2 percent of the cost. At n = 100,000 it is over 99.99 percent. So 7n^2 + 50n + 300 is O(n^2). The "7" and the "50n + 300" are real costs, and at small sizes they matter. Big-O deliberately describes only what happens as n gets large.

The picture of "grows faster"

Here is a chart of several growth rates. Do not memorise it yet; we study each curve in the next lesson. For now notice that the curves that start flat end up on top.

Steps against n for log n, n, n log n, n squared and 2 to the n, with the steeper curves overtaking the flatter ones

An important consequence: a slower-growing algorithm eventually beats a faster-growing one even if it starts with a much bigger constant. An algorithm that takes 1000n steps loses to one that takes n^2 steps when n is below 1,000, but wins for every n above 1,000. Big-O tells you who wins in the long run.

The formal definition, in plain words

You will meet this definition in books and interviews, so here it is carefully. We say

f(n) = O(g(n))

when there are two positive numbers c and n0 such that f(n) <= c * g(n) for every n >= n0.

In words: after some starting size n0, the function f is never above some constant multiple of g. The function g is a ceiling for f, up to a constant factor.

Let us prove that 3n + 10 is O(n). Pick c = 4 and n0 = 10. For every n >= 10, we have 10 <= n, so 3n + 10 <= 3n + n = 4n. The claim holds. The picture shows it: to the right of n0 = 10, the line for 3n + 10 stays under the line for 4n.

The line 3n plus 10 stays below the line 4n for every n from 10 onward

The constants c and n0 are not unique. c = 13 and n0 = 1 also work, because 3n + 10 <= 3n + 10n = 13n once n >= 1. You only need to show that some pair exists.

A computer can check a proposed pair for a range of n. This does not prove the claim for all n, but it is a good way to catch a wrong choice.

c=4,  n0=10 fails at: None
c=4,  n0=5  fails at: 5
c=3,  n0=1  fails at: 1
c=13, n0=1  fails at: None

None means no failure was found. With c = 4 and n0 = 5 the claim breaks at n = 5, because 3*5 + 10 = 25 is bigger than 4*5 = 20. With c = 3 the claim can never hold, because 3n + 10 is always above 3n. Choosing the constants is part of the proof.

Big-O is an upper bound, not a prediction

A common confusion: "O(n^2) means it takes n squared steps". It does not. It means "at most about n squared steps, for large n". Under this definition 3n + 10 is O(n), and it is also O(n^2), and also O(n^3), because a function that stays under a line also stays under a steeper curve. Nobody would say "this loop is O(n^3)" about a single loop, because it is true but useless. We give the tightest bound we can.

Two other symbols describe the other directions.

3n + 10 is Theta(n): it is at most 4n and at least 3n for large n. It is not Theta(n^2), because it does not grow as fast as n squared, and it is not Theta(log n), because it grows faster.

In daily conversation people say "O(n)" when they mean "Theta(n)". Interviewers usually expect the tight one. If your analysis gives you the exact growth rate, say that rate.

Best, worst and average case

The number of steps often depends on which input of size n you got, not just on n. Consider searching for a value in a list.

(0, 1)
(3, 4)
(6, 7)
(-1, 7)

The function returns the index and the number of comparisons. The target at the front took 1 comparison. The target at the back took 7. A missing target also took 7, since the loop checked every item.

• Best case: the target is the first item. 1 comparison, a constant, so O(1).
• Worst case: the target is last or missing. n comparisons, so O(n).
• Average case: if the target is equally likely to be anywhere, you check about half the items. About n/2 comparisons, which is still O(n), because dropping the constant 1/2 leaves n.

When someone says "the complexity of linear search is O(n)", they mean the worst case unless they say otherwise. The worst case is the safe promise: it is the longest you will ever wait. We usually care most about it, because the unlucky input is the one that breaks a system at 3 a.m.

Note the difference between "worst case" and "upper bound". Worst case picks which input to look at. Big-O says how to describe the growth of the function once you picked it. You can give a Big-O for the best case, the worst case, or the average case. They are different questions.

The arithmetic of Big-O

Once the single-loop idea is clear, a handful of rules let you analyse almost anything.

Sequential steps add. If one part takes O(a) and the next takes O(b), the pair takes O(a + b), which is the larger of the two. A loop of n steps followed by a loop of n steps is n + n = 2n, so O(n). A loop of n steps followed by a double loop of n^2 steps is n + n^2, so O(n^2).

Nested steps multiply. If for every pass of an outer part costing O(a) you run an inner part costing O(b), the total is O(a * b). A loop of n passes, each doing a loop of n passes, is O(n^2).

Different inputs get different letters. If a function takes two lists with lengths a and b, do not call both n. A loop over the first list followed by a loop over the second is O(a + b). A loop over the first list with an inner loop over the second is O(a * b). You cannot merge them into one letter, because one list might be tiny while the other is huge.

Constants disappear. A loop that runs 5 times, or 100 times, regardless of the input, is O(1). A loop that runs 3n times is O(n). Even a loop that runs 1,000,000 times regardless of input is O(1) as far as notation goes, although you may not enjoy waiting for it.

Function calls cost what the function costs. If you call a function inside a loop, multiply its cost by the loop count. This catches people out with built-in functions. In Python, x in my_list is a loop over the list. Inside a loop of n passes it becomes n * n.

Let us practise these rules on a set of short snippets. Try to guess each answer before reading the explanation.

3
9
True
False
None

• first_item is O(1). It never looks at more than the first element.
• biggest is O(n). It looks at every element once and does a constant amount of work for each.
• has_pair_with_sum is O(n^2). The outer loop runs n times and the inner loop runs up to n times for each. We will count this one exactly in the next lesson; the answer is about n^2 / 2, which is still O(n^2).
• print_twice is O(n). Two loops one after the other add: n + n = 2n.

The last line prints None because print_twice has no return, and print shows what a function returns. This is not a complexity fact, just a reminder of how Python works.

A checklist for reading any function

When a function is longer than a few lines, work through the same short list every time. It turns a vague feeling into a count.

1. Name the inputs and their sizes. "The list items has n elements. The number k is a value." Write it down, even if only in your head.
2. Mark every loop and every recursive call. For each loop, ask how many passes it makes in the worst case, and write that as a formula in n.
3. Mark every call to a library function. Ask what it does inside. Sorting costs more than one step. Joining strings, slicing and copying lists cost one step per item copied.
4. Combine from the inside out. Start with the innermost loop, find its cost, then multiply by the pass count of the loop around it. Add the costs of parts that run one after another.
5. Keep the biggest term. Drop constants and smaller terms last, not first. Doing it last avoids dropping something that later multiplies.
6. Say the case. Best, worst or average. If you say nothing, you mean the worst case.

Here is the checklist on a function that mixes the ideas. It takes a list of n numbers and reports the smallest gap between any two of them.

1
99

Step through it. The input is the list, size n. There is one loop of about n passes with constant work inside, so O(n). There is one library call, sorted, which we will meet in the next lesson as O(n log n). The two parts run one after the other, so we add: n log n + n. The biggest term is n log n, so the function is O(n log n). The sorted copy also uses n extra slots, which we will count as space later.

The cleverness is worth noticing. A direct method compares every pair, which is O(n^2). Sorting first puts close numbers next to each other, so only neighbours need checking. Paying for a sort once saved us from comparing everything with everything.

An example that changes the answer: duplicates

Here is a task: given a list of numbers, say whether any value appears twice. There is a slow way and a fast way. Both are correct.

True
True
False
False

The slow version compares every pair. For a list with no duplicates that is n(n-1)/2 comparisons: for n = 100,000 about 5 billion. The fast version uses a set, a collection that can answer "have I seen this value?" in about one step. It does n lookups and n inserts, so it takes O(n) steps, about 200,000 operations for the same list.

This is the pattern behind countless interview questions. The brute-force method is correct but quadratic. A clever data structure makes it linear. The trade is memory: the fast version holds up to n values in the set. Faster code often pays with space, which is why the second half of this module covers space too.

(We claimed a set lookup costs "about one step". That is true on average for a hash set, which you will build later in this course. For now, take it as a fact about how Python's set behaves.)

Counting digits: when n is a number, not a list

What is the "size" of the input when the input is a single number? Consider a function that checks whether n is prime by trying every divisor up to n - 1.

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

If n is a prime, the loop runs about n times. So the time is O(n) in the value of n. People write that and it is a fine statement. But a number written in binary is only about log2(n) digits long, and its true "size" as an input is its digit count. Measured against the digit count, a loop that runs n times is exponential. For everyday programming, say "O(n) where n is the value" and move on. If an interview asks why checking primes by trial division is not considered a fast algorithm for huge numbers, the digit-length argument is the answer.

A useful improvement: you only need to try divisors up to the square root of n, because a divisor larger than the square root pairs with a smaller one. That cuts the work to about the square root of n steps, written O(sqrt(n)).

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
True

For n = 1,000,003 the slow version tries over a million divisors in the worst case. The fast one tries at most 1,000. Same answer, a thousand times less work, and the gap widens as n grows.

What happens inside the machine

It helps to connect the abstract count to what the computer does. When Python runs for x in items, the interpreter sets up an iterator, a small object that remembers where it is in the list. Each pass asks the iterator for the next item, stores it under the name x, and runs the body. Each of those is a handful of processor instructions, a few nanoseconds. A nanosecond is one billionth of a second.

A modern computer can do on the order of 10^8 to 10^9 simple operations per second in a compiled language such as C++ or Java, and about 10^7 per second in plain Python, because each Python step costs more instructions. These numbers give you a practical rule of thumb: in a coding contest or interview with a time limit of about one second, a C++ or Java solution can do roughly 10^8 simple steps. We use that figure in the next lesson to decide which complexities are acceptable for which input sizes.

Why do constants not matter then? Because of the shape of the curves. A program that does 100n steps on a fast machine and one that does n^2 steps on a machine ten times faster still cross somewhere. Beyond that point the quadratic program loses and keeps losing by more and more. Buying a faster machine moves the crossing point; it never removes it.

Common mistakes

Mistake 1: forgetting to say what n is. "This is O(n)" means nothing until you say what n is. For a function over a list and a number, the answer might be O(n * k). Always name each input size.

Mistake 2: confusing the value with the size. For range(n) where n is a number, the loop runs n times. For for x in items, the loop runs len(items) times. Both are "n" in casual talk, but they are different n's. Say which one.

Mistake 3: counting loops instead of work. "Two nested loops, so O(n^2)" is a shortcut that is often right and sometimes wrong. A loop that does while d * d <= n is not O(n), and an inner loop that always runs 3 times does not make the pair quadratic. Count how many times the body runs in total.

Mistake 4: forgetting hidden loops. In Python, x in my_list, my_list.index(x), my_list.count(x), sum(my_list), max(my_list), sorted(my_list) and list slicing my_list[a:b] all do work proportional to the length they touch. A loop of n passes that calls one of these is O(n^2), even though no inner for is visible.

# Looks like one loop. Is actually quadratic.
def count_unique(items):
    unique = []
    for x in items:
        if x not in unique:   # hidden loop over unique: up to n steps
            unique.append(x)
    return len(unique)

Mistake 5: believing smaller Big-O always wins. O(n) with a constant of 1,000 loses to O(n^2) with a constant of 1 for n below 1,000. For small inputs, the simple method is often faster. Big-O tells you what happens when the input gets large.

Mistake 6: calling a loop O(1) because "it only runs a few times" when the count depends on the input. If the loop count is tied to n, it is not constant. Only a count that stays fixed for every input is O(1).

Real error messages you will see while experimenting. When you add a step counter, you may hit these.

TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'

This means a variable you meant to use as a counter is None. You probably forgot to write steps = 0 before the loop, or a function returned nothing and you assigned its result. Check the line named in the traceback and look at where that variable got its value.

UnboundLocalError: cannot access local variable 'steps' where it is not associated with a value

You used steps += 1 inside a function, but steps was created outside it. Python treats an assigned name inside a function as local to that function. Either create the counter inside the function, return it, or declare it with global steps (a pattern we avoid in clean code).

IndexError: list index out of range

In linear search code this usually comes from looping range(len(items) + 1) or reading items[index + 1] on the last pass. Complexity analysis does not warn you about off-by-one errors, so test small inputs, including the empty list.

A debugging walkthrough: why is it slow?

Here is a realistic situation. A teammate wrote a function that finds the most common word in a list. It works on a hundred words and takes forever on a hundred thousand. You are asked why.

('a', 3)

Step 1: say what n is. It is the number of words.

Step 2: look for loops. There is one visible for, running n times.

Step 3: look for hidden loops. words.count(w) has to look at every word to count matches. That is n steps, and it happens inside the loop of n passes. So the total is about n * n, or O(n^2). For 100 words that is 10,000 steps, instant. For 100,000 words that is 10 billion steps, which in Python takes minutes.

Step 4: find the repeated work. The program counts the word "the" again every time it meets "the". Counting each word once is enough. Store counts in a dictionary, which finds a key in about one step.

('a', 3)

Step 5: re-count. Two loops one after another, each at most n passes, each pass about 1 step. Total about 2n, so O(n). Same answer, 100,000 words now takes a fraction of a second.

The method generalises. Say what n is. Find every loop, visible and hidden. Multiply nested ones and add sequential ones. Find work that is repeated, and ask whether you can do it once and remember the result.

Where this shows up in real life and interviews

On the job. A report page that loads in 200 ms with 1,000 rows and 20 seconds with 100,000 rows has a quadratic loop somewhere. Database queries get slow when they scan an entire table for each row of another table, which is the same nested loop with different names. Mobile apps stutter when a list of 10,000 items is re-sorted every time the screen redraws. In each case the fix starts with the question this lesson teaches: how does the work grow with the input?

In interviews. After you write a solution, the interviewer nearly always asks "what is the time and space complexity?". Strong answers state both, name what n is, say whether it is the worst case, and mention if a trade could improve it ("I could use a set to bring this from O(n^2) to O(n), at the cost of O(n) extra space"). Weak answers hesitate or give only a guess. You will practise this answer shape in the next three lessons.

In reading code. When you review someone else's code, the first scan is for loops, then for calls inside loops. Learn to do this scan automatically. It catches the single most common performance bug.

Practice

Try each exercise before opening the solution. Exercises are graded from easy to hard.

1. (Easy) What is the Big-O of 5n + 12? Of n^2 + 1000n? Of 4?

2. (Easy) How many times does the line count += 1 run? Give the answer as a number for n = 5, then as a formula.

count = 0
for i in range(n):
    count += 1

3. (Easy) A function does one loop of n passes and then, separately, a loop of 100 passes. What is its complexity?

4. (Medium) Give the complexity of each function, naming n.

def a(items):
    for x in items:
        print(x)
 
def b(items):
    for x in items:
        for y in items:
            print(x, y)
 
def c(items):
    print(items[0], items[-1])

5. (Medium) Two lists have lengths a and b. What is the complexity of printing every pair (x, y) with x from the first list and y from the second? What about printing all of the first list and then all of the second?

6. (Medium) Show that 2n + 6 is O(n) by choosing c and n0 and writing the one-line reason. Then run a small loop to check your pair.

None

7. (Medium) What is the complexity of this function? What is the best case?

def contains_negative(items):
    for x in items:
        if x < 0:
            return True
    return False

8. (Medium) This function is correct but slow for long lists. What is its complexity, and how do you make it faster?

def remove_duplicates(items):
    result = []
    for x in items:
        if x not in result:
            result.append(x)
    return result

[3, 1, 2, 4]

9. (Hard) What is the complexity of this function? Count the exact number of times total += 1 runs for n = 8, then generalise.

def mystery(n):
    total = 0
    i = 1
    while i < n:
        for j in range(n):
            total += 1
        i *= 2
    return total

24 64 10240

10. (Hard) A function is O(n) and takes 2 seconds for n = 1,000,000. Another is O(n^2) and takes 2 seconds for n = 1,000,000 too (it has a tiny constant). Predict the time of each for n = 2,000,000.

What you now know

• Complexity measures how the number of steps grows with the input size, not seconds on a stopwatch.
• You count basic operations, say what n is, and keep only the dominating term with its constant removed.
• Big-O is an upper bound, Omega a lower bound and Theta the tight bound. Worst, best and average case are separate questions.
• Sequential parts add, nested parts multiply, and different inputs need different letters.
• Hidden loops in built-in functions count, and a smarter data structure often turns O(n^2) into O(n).