JAVA-205 · Lesson 1 of 12 · 20 min
Measuring algorithms and Big-O notation
▶ Video coming soon A video version of this lesson is on the way.
Year 2 starts with a problem that StockRoom made visible. StockRoom, the program Hamza built last April, keeps Second Gear's 612 kinds of parts in the right data structures, and it is quick. But Kofi now wants more from it: a reorder report that checks every part against every supplier price list, a check for duplicate codes in the donated-parts log, and a plan for the Saturday pickup runs to partner sites across Hamilton. Some of those jobs could be fast or painfully slow depending on how they are written. On Tuesday, September 14, 2027, at 5:00 pm, before repair night starts, Ingrid begins this term's sessions in the back room with one question: how do you know, before you run a program, how much work it will do?
This course answers that question for the classic algorithms every developer is expected to know: searching, sorting, recursion, divide and conquer, graphs, shortest paths, greedy choices and dynamic programming. Each lesson measures the work an algorithm does by counting operations, not by timing it, and then describes how that count grows with a short formula called Big-O notation.
An algorithm and its input size
An algorithm is a precise, step-by-step method for solving a problem: given any valid input, it finishes and produces the right output. Finding a part by its code, sorting the price list, and finding the quickest route between two partner sites are all problems with several possible algorithms. To compare them, we describe the work each does as a function of the input size, usually written n. For a list of parts, n is the number of parts. For a route map, it may be the number of places and the number of roads between them.
Why not just time the program? Timings depend on the computer, on what else is running, on the Java version and on whether the JVM has warmed up. The same code can take 3 milliseconds once and 9 the next. A count of basic steps, such as comparisons, additions or array reads, does not change from run to run, and it tells you what will happen when the input grows from 612 parts to 6,120 or 61,200. That is the question that matters when you choose an algorithm.
public class Main {
static long steps = 0;
static int total(int[] counts) {
int sum = 0;
for (int c : counts) {
sum += c;
steps++;
}
return sum;
}
public static void main(String[] args) {
for (int n : new int[] {612, 6_120, 61_200}) {
steps = 0;
int[] counts = new int[n];
java.util.Arrays.fill(counts, 3);
int sum = total(counts);
System.out.println("n = " + n + ": total " + sum + ", additions " + steps);
}
}
}n = 612: total 1836, additions 612 n = 6120: total 18360, additions 6120 n = 61200: total 183600, additions 61200
What this code does
The total method adds every count once, and the program counts each addition in the steps field. Ten times as many parts means exactly ten times as many additions. Work that grows in direct proportion to n is called linear.
Counting the work in loops
Most of the work in a program happens in loops, so the first skill is counting how many times a loop body runs. A single loop over n items runs n times. Two loops one after the other run n + n = 2n times. A loop inside a loop is different: if the outer loop runs n times and the inner one runs n times for each outer pass, the body runs n × n = n² times. Kofi's duplicate check is the classic case: compare every code with every later code to see whether two are the same.
public class Main {
public static void main(String[] args) {
String[] codes = {"TUBE-700x25", "BELL", "PAD-ROAD", "CHAIN-11", "BELL", "GRIPS"};
int comparisons = 0;
for (int i = 0; i < codes.length; i++) {
for (int j = i + 1; j < codes.length; j++) {
comparisons++;
if (codes[i].equals(codes[j])) {
System.out.println("duplicate: " + codes[i] + " at " + i + " and " + j);
}
}
}
int n = codes.length;
System.out.println("comparisons: " + comparisons + ", formula n(n-1)/2 = " + n * (n - 1) / 2);
}
}duplicate: BELL at 1 and 4 comparisons: 15, formula n(n-1)/2 = 15
What this code does
The inner loop starts at i + 1, so each pair of positions is compared exactly once. For six codes that is 5 + 4 + 3 + 2 + 1 = 15 comparisons, which matches the formula n(n-1)/2. The program finds BELL at positions 1 and 4.
The formula n(n − 1)/2 is (n² − n)/2. For 6 codes it is 15, which seems harmless. For 612 codes it is 186,966 comparisons, and for the 61,200 lines Kofi expects after a few years of donated-parts logs it is about 1.87 billion. The shape of the formula, not the small example, decides whether the program is usable.
Big-O notation
Big-O notation describes how the work grows when n becomes large, ignoring details that stop mattering. We keep only the fastest-growing term and drop constant factors. The duplicate check does (n² − n)/2 comparisons. The n² term grows fastest, and the factor of one half does not change the shape, so we say the algorithm is O(n²), read as order n squared or quadratic. The total of all counts is O(n), linear. Looking up a value in an array by its index is O(1), constant: it takes the same time however long the array is.
Formally, saying that an algorithm is O(f(n)) means that for large enough n its step count is at most some constant times f(n). Big-O is an upper bound. Two related symbols are useful when you need to be precise. Ω (omega) gives a lower bound: the algorithm needs at least that much work. Θ (theta) means both at once: the work grows exactly like f(n), up to constant factors. The duplicate check is Θ(n²), because it always compares every pair. In everyday speech developers say Big-O when they mean Θ, and this course follows that habit unless the difference matters.
| Big-O | Name | Example in this course | Steps when n = 1,000 |
|---|---|---|---|
| O(1) | Constant | Reading counts[i]; HashMap get, on average | 1 |
| O(log n) | Logarithmic | Binary search in a sorted list (lesson 2) | about 10 |
| O(n) | Linear | Totalling every count; linear search | 1,000 |
| O(n log n) | Linearithmic | Merge sort; Arrays.sort (lesson 4) | about 10,000 |
| O(n²) | Quadratic | Comparing every pair; insertion sort (lesson 3) | 1,000,000 |
| O(2ⁿ) | Exponential | Trying every subset of donated items (lesson 11) | more than 10³⁰⁰ |
public class Main {
public static void main(String[] args) {
System.out.println("n log n n log n n^2");
for (int n = 10; n <= 1_000_000; n *= 10) {
int log = 31 - Integer.numberOfLeadingZeros(n);
long nlog = (long) n * log;
long sq = (long) n * n;
System.out.printf("%-8d %-7d %-13d %d%n", n, log, nlog, sq);
}
}
}n log n n log n n^2 10 3 30 100 100 6 600 10000 1000 9 9000 1000000 10000 13 130000 100000000 100000 16 1600000 10000000000 1000000 19 19000000 1000000000000
What this code does
The program prints how four growth rates compare as n grows from 10 to a million. It works out the whole-number base-2 logarithm with numberOfLeadingZeros, which gives the number of times n can be halved before reaching 1. A million items need only 19 halvings but a trillion steps for a quadratic algorithm.
Logarithms: the cost of halving
A logarithm answers the question: how many times can I halve n before I get down to 1? For n = 8 the answer is 3 (8, 4, 2, 1), and for 1,024 it is 10. In computer science log n means base 2 unless someone says otherwise, and in Big-O the base does not matter, because logarithms in different bases differ only by a constant factor. Any algorithm that throws away half of the remaining work at each step, like binary search in the next lesson, does O(log n) steps.
public class Main {
public static void main(String[] args) {
for (int n : new int[] {8, 612, 61_200, 1_000_000}) {
int remaining = n, halvings = 0;
while (remaining > 1) {
remaining = remaining / 2;
halvings++;
}
System.out.println(n + " can be halved " + halvings + " times");
}
}
}8 can be halved 3 times 612 can be halved 9 times 61200 can be halved 15 times 1000000 can be halved 19 times
What this code does
The loop halves the remaining count until one item is left and counts the halvings. 612 parts need 9 halvings and a million need 19, because integer division rounds down. This is why logarithmic algorithms stay fast even for very large inputs.
Best, worst and average cases
The same algorithm can do different amounts of work on different inputs of the same size. Searching the parts list for a code from the start is quick if the code is first and slow if it is last or missing. We therefore talk about the best case, the worst case and the average case. The worst case is the one usually quoted, because it is a guarantee: whatever the input, the algorithm will not do more. The average case describes typical behaviour, and for some algorithms, such as quicksort in lesson 4 and HashMap lookups from JAVA-201, it is much better than the worst case.
Rules of thumb for counting
- A sequence of steps costs the sum of their costs, and the largest term wins: O(n) followed by O(n²) is O(n²).
- A loop multiplies: a loop that runs n times around an O(log n) step costs O(n log n).
- Constant factors and lower terms are dropped: 3n + 40 is O(n).
- A method call costs whatever the method does: list.contains is O(n) for an ArrayList, so calling it inside a loop over the same list is O(n²).
- Library calls have documented costs: HashMap get and put are O(1) on average, TreeMap operations are O(log n), and sorting objects is O(n log n).
The fourth rule catches many programs. A loop that looks single can hide a second loop inside a method call. Kofi's duplicate check can be made linear by remembering the codes already seen in a HashSet, whose add method reports whether the code was new. That changes O(n²) into O(n) on average, at the price of the memory for the set.
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] codes = {"TUBE-700x25", "BELL", "PAD-ROAD", "CHAIN-11", "BELL", "GRIPS"};
Set<String> seen = new HashSet<>();
int setCalls = 0;
for (int i = 0; i < codes.length; i++) {
setCalls++;
if (!seen.add(codes[i])) {
System.out.println("duplicate: " + codes[i] + " at " + i);
}
}
System.out.println("set operations: " + setCalls);
}
}duplicate: BELL at 4 set operations: 6
What this code does
HashSet.add returns false when the code is already in the set, so the second BELL is reported at position 4. The loop does one set operation per code, six in all instead of fifteen comparisons. For 61,200 log lines this is about 61,200 operations instead of 1.87 billion.
Space as well as time
Big-O also describes memory, called space complexity. The pair-comparing duplicate check uses O(1) extra space: two loop counters, whatever n is. The HashSet version uses O(n) extra space, because in the worst case every code goes into the set. Trading memory for speed like this is one of the most common decisions in algorithm design, and on a laptop with gigabytes of memory a set of 61,200 short strings is usually an easy price to pay.
Try it yourself
Counting a nested loop
Kofi wants to know how many supplier-price checks the reorder report will make. The program checks each of parts parts against each of suppliers price lists. Replace the guess in the starter with a nested loop that counts the checks, and print the count.
With 612 parts and 3 suppliers the program should print checks: 1836.
public class Main {
public static void main(String[] args) {
int parts = 612, suppliers = 3;
int checks = parts + suppliers;
System.out.println("checks: " + checks);
}
}Try it yourself
How many halvings?
Write the method halvings(int n) so it returns how many times n can be divided by 2, rounding down, before it reaches 1.
The program should print 1 0, 2 1, 612 9 and 1000000 19, one pair per line.
public class Main {
static int halvings(int n) {
return n / 2;
}
public static void main(String[] args) {
for (int n : new int[] {1, 2, 612, 1_000_000}) {
System.out.println(n + " " + halvings(n));
}
}
}Common mistakes
MistakeTiming a program once and treating the result as its speed.
InsteadCount operations, or time many runs after warm-up; timings vary between runs and machines.
MistakeKeeping constants and small terms in Big-O, such as O(3n + 40).
InsteadKeep only the fastest-growing term: O(n).
MistakeMissing a loop hidden in a method call, such as list.contains inside a loop.
InsteadAdd up the cost of every call; contains on an ArrayList is O(n).
MistakeAssuming small test data shows how a program will scale.
InsteadWork out the step count formula and try it with the real sizes.
MistakeQuoting only the best case.
InsteadQuote the worst case as the guarantee, and the average case when it is very different.
Summary and key terms
- An algorithm is a step-by-step method that finishes with the right output for every valid input.
- We measure algorithms by counting basic operations as a function of the input size n, because counts do not vary between runs or machines.
- Big-O notation keeps the fastest-growing term and drops constant factors: totalling a list is O(n), comparing every pair is O(n²), and halving the problem each step is O(log n).
- Big-O is an upper bound, Ω a lower bound and Θ an exact growth rate.
- Algorithms can have different best, worst and average cases, and the worst case is the usual guarantee.
- Loops in sequence add, nested loops multiply, and method calls bring their own costs.
- Space can be measured the same way, and trading memory for time, such as using a HashSet to find duplicates in O(n), is a common design choice.
- Algorithm
- A precise, step-by-step method that solves a problem for every valid input and then stops.
- Input size
- The measure of how big the input is, usually called n.
- Big-O notation
- A description of how an algorithm's work grows with n, keeping only the fastest-growing term.
- Constant time
- Work that does not depend on n, written O(1).
- Linear time
- Work that grows in proportion to n, written O(n).
- Quadratic time
- Work that grows with the square of n, written O(n²).
- Logarithm
- The number of times n can be halved before it reaches 1, for base 2.
- Worst case
- The largest amount of work an algorithm does for any input of a given size.
- Average case
- The expected work over typical inputs of a given size.
- Omega and Theta
- Ω is a lower bound on growth; Θ means the growth is both bounded above and below by the same rate.
- Space complexity
- How the extra memory an algorithm uses grows with n.
Practice problems
Work each problem on paper first, then reveal the answer to check.
How many comparisons does checking every pair of 10 codes make?
Show answer
10 × 9 / 2 = 45.
What is the Big-O of an algorithm that does 5n² + 2n + 7 steps?
Show answer
O(n²).
About how many halvings take 1,000,000 down to 1?
Show answer
19, rounding down at each step.
Why is a loop that calls list.contains on an ArrayList of the same size O(n²)?
Show answer
contains walks the list, so each of the n passes does up to n comparisons.
What does the HashSet version of the duplicate check trade for its speed?
Show answer
O(n) extra memory for the set.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.