Problem Size Measurement

Big-Oh notation describes an upper bound on how an algorithm's running time grows as the problem size n increases without limit.

Programming

Why Two Programs Cannot Be Judged by Their Timings

Suppose two programmers each write a function that scans a list and produces a result. One runs her version on a fast laptop and reports that it finished in half a second. The other runs his version on an old machine and reports two seconds. Which algorithm is better? The honest answer is that these numbers cannot settle the question. They mix together two different things: the quality of the method, and the speed of the hardware, the language runtime, and the operating system. A faster computer can make a poor method look excellent for a while.

What do you think happens?

If the laptop version finishes in half a second and the old-machine version finishes in two seconds, what can you conclude about the two methods?

Reveal answer

Answer:

Nothing reliable. The timings mix the quality of the method with the speed of the hardware, so the numbers cannot show which method is better.

A stopwatch measures one machine, one runtime, and one operating system. Changing any of those changes the number even if the method stays the same.

Asking How Running Time Grows

Big-Oh notation was built to avoid this trap. Instead of asking how many seconds a program takes on one particular machine, it asks how the running time grows as the problem gets larger. That shift in question is the foundation of asymptotic analysis, which studies what happens to an algorithm's running time as the problem size increases without limit.

Think of growth as a question about scaling. If you double the number of items you give an algorithm, does its work double, stay roughly the same, or multiply by something much larger? Those answers describe the shape of the running time, and they stay meaningful across machines. A computer that is twice as fast halves every timing, but it does not change whether the work doubles when the input doubles.

How do two algorithms with different constant factors compare on a stopwatch at small inputs, and how does the picture change as n grows?

Choosing the Measure of Problem Size

The letter n in an expression like O(n) stands for the size of the problem. Before any asymptotic analysis can begin, you need a way to measure that size. The source gives a simple rule of thumb: problem size is measured by the number of items for lists, and by the number of bits for integer inputs. Choosing the right measure matters because the analysis is only as meaningful as the size it is counted in.

What the Statement O(f(n)) Promises

Big-Oh notation says that the running time grows no faster than some reference pattern, such as n, n squared, or log n, once scaled by a suitable constant. The source gives the precise version. A statement that the running time is O(f(n)) means that there exist a constant C and a positive integer threshold M such that, whenever n is larger than M, the running time is less than or equal to C times f(n). The source calls the threshold M; this article refers to it as the threshold n0, the form used in most textbooks.

Definition

Big-Oh bound: running time is O(f(n)) when there exist a constant C and a threshold n0 such that running time is at most C times f(n) for every n greater than n0.

Formula

How do the constant C and the threshold n0 make C times f(n) sit above the running time for every n at or beyond n0, even when the actual cost is below it for small n?

The threshold is what makes the statement about the long run. The statement promises nothing about the behaviour below n0, and it does not need to. The constant C absorbs the unknown details. The analysis does not need to know whether a single basic step takes a few nanoseconds or a few milliseconds, nor the exact value of the constant. Those unknown constants are folded into one larger constant, and the growth pattern is what remains.

Tracing a Summing Loop Step by Step

The source describes a summing loop and a general habit for analysing it. Once you have an exact expression for the running time, you find the term that grows fastest as n increases and ignore constant multipliers, because the constant C absorbs them. The same reasoning explains why a fixed setup cost can be folded into the linear term. The example below is an original illustration of that habit; the source does not give this exact code.

python

def sum_list(items):
    total = 0          # fixed setup cost
    for x in items:    # runs n times
        total += x     # constant work per iteration
    return total

def sum_list(items):
    total = 0          # fixed setup cost
    for x in items:    # runs n times
        total += x     # constant work per iteration
    return total

As the loop variable advances on each iteration, how does the number of operations accumulate, and at what point does that total reveal the Big-Oh class?

What do you think happens?

For a list of n items, how many times does the loop body run, and what is the Big-Oh class of sum_list?

Reveal answer

Answer:

The loop body runs n times, once per item. The running time is about n steps plus one fixed setup step, so the Big-Oh class is O(n).

The fixed setup cost of one step is a constant term, which the constant C absorbs. The term that grows with n is the loop, which is linear in n.

Code walkthrough

total = 0 then loop over items then return total

1
The assignment total = 0 runs once, regardless of how long the list is. This is the fixed setup cost.
2
The for loop visits each item once, so the body runs n times for a list of n items.
3
Each pass does a constant amount of work: one addition and one assignment.
4
Total work is about n passes of constant cost plus one setup step, which is linear in n. Dropping the constant and the setup term leaves O(n).

Mistakes Beginners Make With Big-Oh

Common mistake
Reading a timing in seconds as the growth class of an algorithm
Why it fails
A timing mixes the method with the hardware, runtime, and operating system, so it cannot show how running time grows.
Do this instead
Ask how the work changes when the input size doubles, and describe the result as a growth class.
Common mistake
Counting the value of an integer as its size
What it looks like
For the integer 1000000, the value is large but the bit count is only about twenty.
Why it fails
The work of an integer algorithm depends on how many bits represent the number, not on its magnitude.
Do this instead
Use the number of bits as n for integer inputs.
Common mistake
Thinking O(f(n)) describes behaviour for every input size
Why it fails
The definition only requires the bound to hold for n greater than the threshold n0.
Do this instead
Read O(f(n)) as a claim about large inputs only.
Common mistake
Keeping constant multipliers in the final class instead of absorbing them into C

Comparing Growth Patterns

The three patterns named in the source sit at different points on a scale of growth. O(log n) grows very slowly, because the logarithm of n increases only a little when n increases a lot. O(n) grows in step with the problem size. O(n squared) grows with the square of the problem size, so doubling n roughly quadruples the bound.

Growth class	Effect of doubling n	Example reading
O(log n)	bound rises by only a little	very slow growth
O(n)	bound doubles	grows in step with size
O(n squared)	bound roughly quadruples	grows with the square of size

Three growth patterns from the source, compared by what doubling n does.

Practice Measuring and Classifying

EASY

A function receives a list of 12 names and loops through them once, printing each name. Find n and state the Big-Oh class of the running time.

Hints

For a list input, n is the number of items.
The loop body runs once per name, so the running time grows with the number of names.
Constant work per iteration is absorbed into C, leaving a term that grows with n.

Your attempt (not saved)

MEDIUM

An algorithm checks whether an integer is prime. Explain in one sentence why the problem size is the bit count of the integer rather than its value, and say which quantity you would change to test how the running time scales.