Time complexity and counting steps

An algorithm is a list of steps that solves a problem. Time complexity says how the number of steps grows as the input gets bigger. It matters because a method that feels instant on ten items can freeze on ten million.

A shop's search page looks through its products every time someone types. Counting the steps tells you, before you run anything, whether it will still work when the shop grows.

A step is one small action: one comparison, one addition, one list item looked at. Seconds change with the machine, but the number of steps does not.

So to judge an algorithm you count its steps for an input of size n. For a list, n is the number of items.

# Count the steps of a loop that adds up some prices.
prices = [4, 9, 2, 7, 5]
steps = 0
total = 0
for price in prices:
    total = total + price
    steps = steps + 1
print("total", total, "steps", steps)
# Change prices to ten numbers, then press Run again.

What matters is how the count changes when n doubles. A loop over the list takes twice as many steps for twice the items. That is linear growth.

A loop inside a loop takes n times n steps. Double the items and the steps become four times as many. That is quadratic growth.

# Count the steps of a loop inside a loop.
n = 5
steps = 0
for i in range(n):
    for j in range(n):
        steps = steps + 1
print("n", n, "steps", steps)
# Change n to 10, then press Run again.

In the lab, seq 1 5 writes the numbers 1 to 5, one per line, and wc -l counts lines. Together they count to five.

The second Run does the quadratic sum: a thousand rows of a thousand columns is a million cells.

seq 1 5 | wc -l

python3 -c "print(1000 * 1000)"

Steps are exact. Time is not, because it depends on the machine and on what else it is doing.

The time word before a command prints three lines after it ends: real, user and sys. Read the real line. The numbers will be yours alone, so run it twice and expect small differences.

time seq 1 100000 | wc -l

time seq 1 1000000 | wc -l

Big O notation is a short way to write the growth. You drop the small parts and the constant numbers, because for a big n they hardly matter.

An algorithm of 3n + 5 steps is O(n), said "order n". One of n times n plus 3n steps is O(n squared).