Why we measure growth, not seconds
On This Lesson 11 topics
Lesson Overview
In BEG-017 you counted comparisons in four algorithms and saw that some of them barely notice more data while others choke on it. This module turns that informal feeling into a skill: describing how fast the work of a piece of code grows as its input grows, and using that description to choose between two solutions.
This first lesson answers one question: why do we count steps and look at growth instead of just timing the code with a stopwatch? You will see a stopwatch give three different answers for identical code, and you will see two algorithms whose step counts tell a story no stopwatch can.
Why this matters: a backend service that is fast with 100 test rows can fall over with 10 million real ones. Growth is the tool that predicts that before it happens.
This lesson builds on "Counting steps: a first look at efficiency" (BEG-017) and on timing with System.nanoTime() (BEG-030).
Learning Objectives
By the end of this lesson you will be able to:
- Define an algorithm, an input size (
n), and a step. - Explain why a single timing is a weak way to compare algorithms.
- Count the steps an algorithm takes for several input sizes and put them in a table.
- Describe growth in words: stays almost flat, grows in step with
n, or grows much faster thann. - Predict which of two algorithms wins on large input even when it runs on a slower computer.
- Say what a step count cannot tell you, and when a timing is still useful.
Written Explanation
Three words to fix first
An algorithm is a step-by-step recipe for solving a problem, for example "look through the list from the start until you find the name". The input size, written n, is how much data the recipe works on: the number of names in the phone book, the length of an array, the number of rows returned by a query. A step is one small, basic action that takes about the same time every time, such as one comparison or one array read.
Counting steps is the same idea as the counter you added in BEG-017. What is new is the goal: not the count for one input, but how the count changes when n changes. That change is called the growth of the algorithm.
Why seconds are a weak measure
Suppose a colleague says: "my search took 2 seconds, yours took 3, so mine is better." That sentence hides several problems.
- The machine matters. A laptop, a phone, and a cloud server run the same code at different speeds.
- Everything else running matters. Other programs, the operating system, and the Java runtime's own start-up work (the warm-up you met in BEG-030) all add noise.
- The input matters. Two algorithms might be close on 1,000 items and wildly different on 1,000,000, and one timing tells you about one size only.
The Java documentation for System.nanoTime() is clear about what it offers: it is meant for measuring elapsed time as the difference between two readings, and it promises nanosecond precision but not necessarily nanosecond resolution. In other words, it is a good ruler for a rough check, not a guarantee of exact, repeatable numbers.
A step count has none of these problems. It does not depend on the machine, the noise, or luck. What it needs from you is the input size, and that is exactly the thing we want to ask about.
The phone-book picture
A phone book has its names in alphabetical order. Two ways to find a name:
- Read every name from the first page until you find it (linear search).
- Open the book in the middle, see whether your name comes before or after, throw away the wrong half, and repeat (binary search, the algorithm of BEG-017-L03).
Ask how many steps each needs for a name that is not in the book at all, the demanding case.
Names in the book (n) | Read every name | Halve each time |
|---|---|---|
| 10 | 10 | 3 |
| 1,000 | 1,000 | 9 |
| 1,000,000 | 1,000,000 | 19 |
These are real counts from running the two methods below on sorted arrays (they are the same numbers the BEG-017 experiment found). Look at the pattern:
- Read every name: ten times more names means ten times more steps. The work grows in step with
n. - Halve each time: from 1,000 names to 1,000,000 (a thousand times more) the count rises from 9 to 19. Doubling the data adds one step. The work barely grows.
The shape of that growth is what carries over to every machine, every language, and every year. The exact seconds do not.
Growth beats raw speed
Here is the most useful consequence. Imagine, as a thought experiment with assumed numbers, a very fast computer that performs one billion steps per second reading every name in a book of one billion names. That takes about one second. Now take a computer a thousand times slower, one million steps per second, running the halving search on the same book. Halving needs about 30 steps for a billion names, so it finishes in about 30 millionths of a second.
The slow machine with the better algorithm wins by a huge margin, and it would still win if we made the fast machine ten times faster. Hardware gives you a constant factor, such as "a thousand times faster". A better growth rate gives you a factor that keeps widening as n grows. For large data, growth wins.
What step counting does not tell you
Be honest about the limits:
- A step count says nothing about the cost of one step: reading a number from memory and reading a row across a network are both "one step", yet differ enormously.
- For small
nthe "better" algorithm can lose: the halving search needs a sorted book, and sorting costs work too. - Growth predicts the trend. When two options have the same growth, a timing on real data is how you pick between them.
So the working method is: use step counts and growth to choose a direction, use timings to confirm that the real program behaves as predicted.
Examples
Example 1: a table by hand (simple)
Reading every name needs, at worst, one step per name. Halving needs the number of times you can cut n in half until one name is left. For 8 names: 8, 4, 2, 1, so about 3 cuts. For 16 names: 16, 8, 4, 2, 1, so about 4. Each doubling of the book adds one cut.
n | 8 | 16 | 32 | 64 |
|---|---|---|---|---|
| Read every name | 8 | 16 | 32 | 64 |
| Halve each time (cuts) | 3 | 4 | 5 | 6 |
The first row doubles with n. The second row goes up by exactly one.
Example 2: three different answers from one program (practical)
The program below counts steps and times the "read every name" method on an array of five million numbers. The method is the same in every run.
static long steps;
static boolean readAll(int[] a, int target) {
for (int x : a) {
steps++; // one step per element read
if (x == target) return true;
}
return false;
}Timing the same call five times on JDK 21 (a Windows laptop; your numbers will differ) printed:
run 1: 6817 us
run 2: 2654 us
run 3: 3063 us
run 4: 3037 us
run 5: 5169 usThe units are microseconds, millionths of a second. The slowest run took more than two and a half times as long as the fastest, for identical code and identical data. The step count, steps, was exactly 5,000,000 every time. If you had timed once and compared against another algorithm's single timing, you could easily have drawn the wrong conclusion. This is the warm-up and noise problem from BEG-030 seen again.
Example 3: counting a growing input (realistic)
A fuller version of the program counts both methods for the three sizes of the table above. The halving method is binary search written as a loop:
static boolean halve(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
steps++; // one step per look
int mid = (lo + hi) >>> 1;
if (a[mid] == target) return true;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}Calling both with the missing target -1 on arrays {0, 2, 4, ...} of size 10, 1,000, and 1,000,000 printed:
10 readAll=10 halve=3
1000 readAll=1000 halve=9
1000000 readAll=1000000 halve=19Now read it as a backend engineer. If a service searches a sorted list of a million IDs on every request, the first method does a million steps per request and the second does 19. The step counts predict this before you deploy, and they explain the result of any later timing.
Backend Insight
Capacity problems are almost always growth problems. A service that handles 50 requests a minute is not stressed by an inefficient method; the same method at 5,000 requests a minute, on data that has grown tenfold, may be. When data and traffic grow together, work that grows in step with n becomes noticeable, and work that grows much faster than n becomes an outage.
Two habits follow from this lesson:
- When reviewing code, ask "what happens to the work if this data becomes 100 times bigger?" before asking "how fast is it today?"
- Test with realistic sizes. A method that is fine on 20 rows in a unit test may take minutes on 20 million rows.
Common Mistakes
Mistake 1: Comparing two single timings
- Incorrect: "Version A took 12 ms and version B took 15 ms, so A is better."
- Correct: "Repeat each several times, on the same data, and compare the trend as the size grows."
Mistake 2: Testing on one small input
A comparison on 10 items can show the "wrong" winner or no difference at all. Growth only shows up as n gets large, so compare at several sizes.
Mistake 3: Believing a faster computer fixes a bad growth rate
Hardware changes the speed of one step by a constant factor. If the work grows much faster than the data, a faster machine buys you a short delay, not a solution.
Exercises
Try each exercise yourself before opening the solutions.
Level A: Foundation
A1. Define algorithm, input size, and step in one sentence each, using a search through a list of customers as the example.
Show solution A1
A1. The algorithm is the recipe "check each customer from the start until the ID matches". The input size is the number of customers, n. A step is one comparison of the wanted ID with a customer's ID.
A2. Give two reasons a single timing of 2 seconds is a poor way to compare two algorithms.
Show solution A2
A2. Any two of: it depends on the machine; other running programs and the Java warm-up add noise; it tells you about one input size only; running again gives a different number.
A3. A method needs 10 steps for 10 items, 20 for 20, and 30 for 30. Does the work grow in step with n, barely grow, or grow much faster than n?
Show solution A3
A3. It grows in step with n: the steps equal n every time.
Level B: Application
B1. Method P takes 4, 5, 6, and 7 steps for n = 16, 32, 64, and 128. Method Q takes 16, 32, 64, and 128 steps for the same sizes. Which has the better growth? Predict P's and Q's steps for n = 256.
Show solution B1
B1. P has the better growth: it adds one step each time n doubles, while Q doubles. For n = 256: P takes 8 steps, Q takes 256.
B2. You time a method three times and get 40, 35, and 90 microseconds. What probably explains the odd one, and what would you do before trusting any of the numbers?
Show solution B2
B2. The 90 is probably noise or warm-up (another program running, or the runtime still optimizing the code). Run the method several times, discard the first run when the work is small, and look for a repeatable result before comparing anything.
B3. In the thought experiment of this lesson the slow machine with the halving search beat the fast machine with the read-everything search. Would a machine ten times faster than the fast one change the winner for a book of one billion names? Show the numbers.
Show solution B3
B3. A machine ten times faster does 10 billion steps per second, so reading a billion names takes about 0.1 seconds. The slow machine with halving needs about 30 steps at one million steps per second, which is 0.00003 seconds. Halving still wins by a factor of several thousand. Better hardware shrinks the gap by a constant; it does not close it.
Level C: Challenge
C1. Write a method static int stepsToFind(int[] a, int target) that returns how many array elements a linear search reads before it stops (including the match, or the whole array if missing). Print its result for the target -1 on arrays of size 100, 200, and 400, and describe the growth in words.
Show solution C1
C1.
static int stepsToFind(int[] a, int target) {
int steps = 0;
for (int x : a) {
steps++;
if (x == target) return steps;
}
return steps;
}For a missing target, sizes 100, 200, and 400 give 100, 200, and 400 steps. The steps double when n doubles, so the growth is in step with n.
C2. A teammate says: "Our endpoint did 800 ms on my laptop, so it will be fine in production since the server is faster." Write three sentences explaining what they have overlooked about growth, using your own example numbers.
Show solution C2
C2. The 800 ms is the answer for one input size on one machine. In production the table may hold a hundred times more rows, and if the work grows in step with the data it becomes about 80,000 ms, or if it grows like n times n far more. A server that is two or three times faster only divides that by two or three, so the growth, not the machine, decides whether the endpoint survives.
Mini Challenge
Take any search you wrote in BEG-017 (linear or binary) and make a table like the one in this lesson.
- Add a
stepscounter to the method, reset it before each run, and call the method forn= 10, 100, 1,000, and 10,000 with a target that is not in the array. - Write the four counts in a table and add a sentence in words: "when
nis multiplied by 10, the steps are ...". - Time the same method once for
n= 1,000,000 withSystem.nanoTime(), three times in a row, and write down all three numbers.
Check your work: the counts are the same each time you run the program; the timings are not.
Summary & Next Lesson
Key takeaways
- An algorithm is a recipe;
nis the input size; a step is one basic action. - Seconds depend on machine, noise, and input size. Step counts depend only on the algorithm and
n. - Growth is how the number of steps changes when
nchanges, for example "in step withn" or "one more step per doubling". - A better growth rate beats faster hardware once
nis large. - Step counts predict the trend; timings confirm it.
Next lesson
The next lesson, "Big O notation", gives these growth shapes short standard names and the rules for writing them, so you can say "O(n)" or "O(log n)" instead of long sentences.
Self-check
- Why does a faster computer not rescue a bad growth rate?
- What does the table of steps for the halving search show about doubling
n? - Name two reasons a timing can change between identical runs.
- A method takes 50, 100, and 200 steps for
n= 50, 100, and 200. How does it grow? - When is a timing still the right tool?
Show answers
- A faster computer makes each step cheaper by a constant factor, while a worse growth rate multiplies the work as
ngrows, so the gap keeps widening. - Each doubling of
nadds only about one step. - Other programs running, the Java runtime's warm-up, the state of the machine; any two of these.
- In step with
n: the steps equaln. - To confirm that the real program behaves as the step counts predict, and to choose between two options with the same growth.
References
- Oracle, System (Java SE 21 API). The
nanoTime()documentation says it measures elapsed time as a difference between two readings and gives nanosecond precision without guaranteeing nanosecond resolution. - Princeton University, Analysis of Algorithms (Algorithms, 4th edition). It supports choosing a cost model by counting basic operations, and presents order of growth as the simplified description of how cost depends on input size.
- The phone-book picture, the one-billion-name thought experiment (its machine speeds are assumed numbers), and the timing run on JDK 21 are this course's own. All counts and timings shown were produced by running the code on one Windows machine with JDK 21; timings will differ on yours.
Practice
Apply this lesson with the module's lab, exercises and quiz.
Marking a lesson complete is optional and you can undo it any time. Your progress stays in this browser.