Constant and Linear Time

Your code runs in 2 milliseconds on your laptop with 100 test records. Will it survive a customer with 10 million records? A stopwatch cannot tell you, because the answer depends on the machine. Computer scientists ask a better question: how does the work grow as the input grows? The two simplest answers are constant and linear.

The rule

Double the input and watch the work: unchanged is constant, doubled is linear.

Call the input size n: the number of items in a list, characters in a string, rows in a table.

• Constant time, written O(1): the work does not depend on n. Reading a[5], adding two numbers, or checking whether a list is empty all take the same time for 10 items or 10 million.
• Linear time, written O(n): the work grows in step with n. Summing a list, finding its largest value, or searching an unsorted list for a name all touch each item once.

We count steps, not seconds, and we ignore constant factors. A loop that does 3 small steps per item does 3n steps; that is still linear, because doubling n still doubles 3n. What matters is the shape of the growth, not the exact count.

The shortcut

Run the doubling test in your head: imagine the input twice as large and ask what happens to the work.

The trap is being fooled by a loop. A loop only makes code linear if the number of times it runs grows with n. A loop with a fixed count, like "the first 10 items", is constant.

Drills

Answer fast — trust the rule.

Remember

• Double the input: unchanged work is constant, doubled work is linear.
• Count steps, not seconds, and drop constant factors: 5n is linear.
• The trap: a loop with a fixed count is constant, not linear.