Time and Space Complexity (Big-O) in Java

Suppose a teacher needs to find one student's answer sheet. If the sheets are in a random pile, the teacher may have to look at every sheet. If they are sorted by roll number, the teacher can open the pile in the middle and halve the search each time. With 40 sheets the difference is small. With 40,000 sheets, it is the difference between an afternoon and a few seconds. Big-O notation is the language programmers use to describe exactly this: how the work grows when the input grows. In this lesson, you will learn what time and space complexity mean, the common Big-O classes, and how to work out the Big-O of a piece of Java code.

What Is Big-O Notation?

Big-O notation in Java (and in computer science generally) is a way of describing how the number of steps an algorithm takes, or the memory it uses, grows as the input size n grows. It ignores exact timings, which depend on the computer, and focuses on the shape of the growth.

• Time complexity: how the number of steps grows with n.
• Space complexity: how the extra memory grows with n (not counting the input itself).

Big-O usually describes the worst case: the most work the algorithm can need for an input of size n.

The Common Classes

Counting Steps in Code

Let's see an example that counts how many times the innermost line runs for three common loop shapes.

public class Growth {
    static long linear(int n) {
        long steps = 0;
        for (int i = 0; i < n; i++) {
            steps++;
        }
        return steps;
    }
 
    static long nested(int n) {
        long steps = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                steps++;
            }
        }
        return steps;
    }
 
    static long halving(int n) {
        long steps = 0;
        for (int i = n; i > 1; i /= 2) {
            steps++;
        }
        return steps;
    }
 
    public static void main(String[] args) {
        System.out.printf("%8s %10s %12s %8s%n",
                "n", "O(n)", "O(n^2)", "O(log n)");
        for (int n : new int[] {10, 100, 1_000, 10_000}) {
            System.out.printf("%8d %10d %12d %8d%n",
                    n, linear(n), nested(n), halving(n));
        }
    }
}

       n       O(n)       O(n^2) O(log n)
      10         10          100        3
     100        100        10000        6
    1000       1000      1000000        9
   10000      10000    100000000       13

Explanation:

1. linear runs its body once per element: 10 times more input means 10 times more steps. That is O(n).
2. nested runs the inner loop n times for each of the n outer steps: n × n. Ten times more input means 100 times more steps. That is O(n²).
3. halving divides i by 2 each time, so it needs only about log₂ n steps. Going from 1,000 to 10,000 adds just 4 steps. That is O(log n).

Rules for Working Out Big-O

The last rule catches many people. A single line can hide a whole loop: list.contains, list.remove(0) on an ArrayList, String.indexOf, and stream().filter(...).count() all look at many elements. See "Time Complexity of Collection Operations" for the cost of every common collection method.

Space Complexity

Space complexity counts the extra memory an algorithm needs as n grows.

Often you can trade one for the other: a HashSet uses O(n) extra memory to turn repeated O(n) lookups into O(1) ones.

Best, Average and Worst Case

When someone says "this is O(n)" without saying which case, they almost always mean the worst case.

Interview Corner

Practice

1. Easy: Add a method cubic(int n) with three nested loops to Growth.java and add a column for it. How many steps does it take for n = 100?
2. Harder: Work out the Big-O of a method that loops i from 1 to n, and inside it loops j from 1 while j < n, doubling j each time. Then count the steps in code to check your answer.

Key Takeaways