Algorithm Running Time Analysis

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 Stopwatch Numbers Mislead

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, because 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. A stopwatch reading tells you how one program behaved on one machine on one day. It does not tell you how the method itself will behave as the work 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.

How do the two programmers' timings differ from one machine to another, and how does the growth rate of a method stay the same across machines as n increases?

Growth as a Question About Scaling

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.

This is why the analysis attaches a description of growth to an algorithm rather than a fixed number of seconds. Big-Oh is the tool for stating an upper limit on that growth. It says that, eventually, the running time will not climb faster than some chosen reference pattern, such as n, n squared, or log n, once scaled by a suitable constant.

The three reference patterns named in the source sit at different points on a scale of growth. O(log n) grows very slowly, since the logarithm of n increases only by 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.

Measuring the Size n

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. In many cases the choice is obvious. If the task is to sort a list of items, the natural size is the number of items in the list. Each extra item is more work the algorithm must handle, so counting items reflects the difficulty of the task.

Reading a Big-Oh Statement

A statement that the running time is O(f(n)) means that beyond some threshold, the running time is at most a constant multiple of f(n). The exact version uses two quantities. There must 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).

Rule

Each part of the statement has a job. The constant C absorbs machine speed, compiler details, and the unit of time, so the statement does not depend on any particular timing. The threshold M is what makes the statement about the long run. The statement promises nothing about the behaviour below M, and it does not need to.

Notice what the analysis did not need. It did not need to know whether one basic step takes 3 nanoseconds or 3 milliseconds, and it did not need to know the exact value of C. The unknown constants are folded into one larger constant, and the growth pattern is what remains.

Tracing a Summing Loop

Now apply the idea to a concrete loop. The function below adds up every value in a list. Before the loop starts there is one fixed setup step, and then the loop body runs once for each item.

python

def total(values):
    result = 0
    for value in values:
        result = result + value
    return result

def total(values):
    result = 0
    for value in values:
        result = result + value
    return result

Notes on the code

result = 0 is the fixed setup cost, paid once no matter how long the list is
The loop header runs the body once per element of values
Each pass does one addition, which is a constant amount of work

Worked example

Counting Steps for a Four-Item List

Count the basic operations when total is called on a list with n = 4 items, then generalise to any n.

1
Count setup
result = 0 is one operation.
2
Count the loop
The loop runs once for each of the 4 items, and each pass does one addition, giving 4 operations.
3
Add the totals
The total is 1 + 4 = 5 operations.
4
Generalise
For any list of n items the total is 1 + n operations. The fixed 1 is a constant that does not depend on n.
5
Find the Big-Oh class
Keep the term that grows fastest with n and drop the constant. The term n grows fastest, so the running time is O(n). Choosing C = 2 and M = 1 works, because 1 + n is at most 2n whenever n is at least 1.

Result

The summing loop runs in 1 + n operations and is O(n)

How does the number of operations change at each iteration as n grows, and how do the counted steps add up to a total whose Big-Oh class is O(n)?

Read the diagram from left to right. The setup is paid once. Each iteration adds one more unit of work, so the running count grows in step with n. The fixed setup cost is absorbed into the linear term, which is the same habit the source describes: keep the fastest-growing term and ignore the constant multipliers.

Mistakes When Reading Big-Oh

Common mistake
Comparing algorithms by a single stopwatch reading
What it looks like
Reporting that one scan took half a second and another took two seconds, then declaring the first method better.
Why it fails
The timings mix the method with the hardware, the runtime, and the operating system.
Do this instead
Describe how the running time grows as n increases, since that shape holds across machines.
Common mistake
Counting the size of a list by the values in it
What it looks like
Saying a list of four very large numbers has a larger n than a list of four small numbers.
Why it fails
For lists, n is the number of items, which is the count the algorithm must handle.
Do this instead
Set n to the number of elements in the list.
Common mistake
Using the integer's value as the size of an integer input
What it looks like
Treating 725 as n = 725 when checking whether it is prime.
Why it fails
The work depends on how many bits the integer takes to write down.
Do this instead
Use the bit count, which is 10 for the integer 725.
Common mistake
Assuming a Big-Oh bound holds for small inputs
Why it fails
The definition only promises the bound beyond a threshold M.
Do this instead
Check the threshold: the statement applies only for n larger than M.

Predicting a Nested Loop

What do you think happens?

A loop runs n times, and inside it a second loop also runs n times. What is the Big-Oh class of the total running time?

O(n)
O(log n)
O(n squared)
O(1)

Reveal answer

Answer:

O(n squared)

The inner loop runs n times for each of the n outer passes, so the total number of inner steps is n times n, which is n squared. Doubling n roughly quadruples this count, which is the O(n squared) pattern described earlier.

MEDIUM

Trace a loop that sets total to 0, then loops over a list of n items and adds 2 to total on each pass. Count the operations as 1 + n, decide which term grows fastest, and state a constant C and threshold M that make the running time at most C times f(n) for n greater than M.

Hints

Count the setup step separately from the loop body.
The loop body runs once per item, so the loop contributes n operations.
Try C = 2 and M = 1, and check that 1 + n is at most 2n for every n above M.

Your attempt (not saved)

Key Takeaways

A stopwatch timing mixes the quality of a method with the hardware, runtime, and operating system, so it cannot fairly compare algorithms; growth-based description is used instead.
For a list, the problem size n is the number of items; for an integer input, n is the number of bits needed to write it down.
A statement that the running time is O(f(n)) means that beyond a threshold M, the running time is at most a constant C times f(n), and it says nothing about small inputs.
To find the Big-Oh class of a loop, count the operations as an expression in n, keep the term that grows fastest, and drop the constant multipliers.