Time Complexity in Data Structures

Time complexity in data structures describes how the number of steps an operation performs grows as the input size n grows. It is written in Big-O notation, such as O(1), O(log n), O(n) or O(n²), and it tells you whether an operation will stay fast when your data grows from a hundred items to a million.

Why Count Steps Instead of Seconds?

A stopwatch measures one run on one machine. Time complexity measures the shape of the growth, which is the same on every machine. If a method does 10 steps for 10 items and 1,000,000 steps for 1,000 items, no faster CPU will rescue it when the data reaches a million items. The performance analysis tutorial explains this idea in more detail; this page focuses on working out the time complexity of real Java code.

How to Find the Time Complexity of Java Code

You do not need to count every single instruction. A handful of rules covers almost all code you will meet:

1. Simple statements cost O(1). An assignment, a comparison, an arithmetic operation or reading array[i] takes constant time.
2. A loop multiplies. The cost of a loop is the number of iterations times the cost of its body.
3. Nested loops multiply again. A loop of n inside a loop of n costs n × n = n².
4. Blocks in sequence add. Code that runs one block after another costs the sum, and the largest term wins: O(n) + O(n²) is O(n²).
5. A loop that multiplies or divides its counter is logarithmic. If i doubles or halves on every pass, the loop runs about log₂ n times.
6. For if/else, take the more expensive branch when you want the worst case.
7. Drop constants and smaller terms. 3n + 5 becomes O(n), and n²/2 + n becomes O(n²).

Here is a method annotated with these rules:

public class StepRules {

    static int sumAndCountPairs(int[] values) {
        int total = 0;                          // 1 step
        for (int v : values) {                  // n iterations
            total += v;                         //   1 step each  -> n
        }
        int pairs = 0;
        for (int i = 0; i < values.length; i++) {          // n iterations
            for (int j = i + 1; j < values.length; j++) {  //   up to n each
                pairs++;                                    //   -> about n²/2
            }
        }
        return total + pairs;                   // 1 step
    }
}

The first loop costs n steps, the nested loops cost about n²/2 steps, and the remaining statements cost a constant. Adding them gives roughly n²/2 + n + 2, and keeping only the fastest-growing term gives O(n²).

When two loops depend on different inputs, keep both variables. A loop over n orders followed by a loop over m customers is O(n + m); the same loops nested are O(n × m). Writing O(n²) in that case would hide which input actually drives the cost.

Common Time Complexities in Java

The program below turns each common complexity into a loop pattern and counts how many times the innermost statement runs. Counting, rather than timing, gives the same numbers on every computer.

public class LoopPatternCounter {

    // O(1): the amount of work does not depend on n
    static long constant(int n) {
        return 1;
    }

    // O(log n): the loop variable doubles each time
    static long logarithmic(int n) {
        long steps = 0;
        for (int i = 1; i < n; i *= 2) {
            steps++;
        }
        return steps;
    }

    // O(n): one pass over the input
    static long linear(int n) {
        long steps = 0;
        for (int i = 0; i < n; i++) {
            steps++;
        }
        return steps;
    }

    // O(n log n): a linear loop around a logarithmic loop
    static long linearithmic(int n) {
        long steps = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j *= 2) {
                steps++;
            }
        }
        return steps;
    }

    // O(n^2): a full loop inside a full loop
    static long quadratic(int n) {
        long steps = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                steps++;
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        System.out.printf("%7s %6s %9s %11s %13s %15s%n",
                "n", "O(1)", "O(log n)", "O(n)", "O(n log n)", "O(n^2)");
        for (int n : new int[] {16, 1_024, 65_536}) {
            System.out.printf("%,7d %,6d %,9d %,11d %,13d %,15d%n", n,
                    constant(n), logarithmic(n), linear(n), linearithmic(n), quadratic(n));
        }
    }
}

      n   O(1)  O(log n)        O(n)    O(n log n)          O(n^2)
     16      1         4          16            64             256
  1,024      1        10       1,024        10,240       1,048,576
 65,536      1        16      65,536     1,048,576   4,294,967,296

Read the table column by column. Multiplying n by 4,096 (from 16 to 65,536) leaves O(1) unchanged, adds only 12 steps to O(log n), multiplies O(n) by 4,096, and multiplies O(n²) by almost 17 million. That last column is why a quadratic algorithm that feels instant in a unit test can freeze a production server.

Time Complexity of Recursive Methods

For a recursive method, count how many calls are made and how much work each call does outside its recursive calls. Four shapes appear again and again:

A quick way to see this is to draw the recursion tree. Merge sort has log₂ n levels, and each level does n work in total, so it costs n × log n. Naive Fibonacci's tree roughly doubles at every level, so the number of calls explodes. Storing each answer the first time it is computed (memoization) makes every Fibonacci value cost O(1) after the first, bringing the whole computation down to O(n).

Time Complexity of Java Collection Operations

Most performance bugs in Java applications come from choosing a collection whose common operation is slow. These costs come from the Java SE API documentation:

Sorting is O(n log n) in both main library methods: Collections.sort and Arrays.sort for objects use a merge-sort variant (TimSort), and since Java 14 the documentation of Arrays.sort(int[]) guarantees O(n log n) on all data sets.

Hidden Loops That Change the Time Complexity

A single line of Java can hide a loop. When that line sits inside your own loop, the complexity jumps a level without any visible nested for. These are the cases most tutorials leave out:

• list.contains(x) inside a loop. On an ArrayList, contains scans the list, so calling it n times is O(n²). A HashSet lookup is O(1) on average.
• list.remove(0) inside a loop. Removing the first element of an ArrayList shifts all the others, so draining a list this way is O(n²). An ArrayDeque removes from the front in O(1).
• result += text inside a loop. A String is immutable, so every += builds a new string and copies all the characters collected so far. Building a string of n pieces this way copies about n²/2 characters. A StringBuilder appends in amortized O(1).

The program below checks a list of order numbers for duplicates in two ways: by comparing every pair, and by remembering the numbers already seen in a HashSet. It counts the comparisons in the worst case, when no number repeats.

import java.util.HashSet;
import java.util.Set;

public class DuplicateOrderFinder {

    static long comparisons;

    // Compares every pair of order numbers: O(n^2)
    static boolean hasDuplicateNested(int[] orders) {
        for (int i = 0; i < orders.length; i++) {
            for (int j = i + 1; j < orders.length; j++) {
                comparisons++;
                if (orders[i] == orders[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    // Remembers what it has seen in a HashSet: O(n) on average
    static boolean hasDuplicateWithSet(int[] orders) {
        Set<Integer> seen = new HashSet<>();
        for (int order : orders) {
            comparisons++;                 // one hash lookup per order
            if (!seen.add(order)) {        // add() returns false if already present
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        for (int n : new int[] {1_000, 10_000, 100_000}) {
            int[] orders = new int[n];
            for (int i = 0; i < n; i++) {
                orders[i] = 50_000 + i;    // all different: the worst case
            }
            comparisons = 0;
            hasDuplicateNested(orders);
            long nested = comparisons;

            comparisons = 0;
            hasDuplicateWithSet(orders);
            long withSet = comparisons;

            System.out.printf("n = %,7d  nested loops: %,13d   HashSet: %,7d%n", n, nested, withSet);
        }
    }
}

n =   1,000  nested loops:       499,500   HashSet:   1,000
n =  10,000  nested loops:    49,995,000   HashSet:  10,000
n = 100,000  nested loops: 4,999,950,000   HashSet: 100,000

Ten times more orders means a hundred times more work for the nested loops, but only ten times more work for the HashSet version. At 100,000 orders that is nearly five billion comparisons against one hundred thousand. The HashSet version pays for its speed with O(n) extra memory, which is the classic time-for-space trade-off.

Related Tutorials

• Performance analysis in data structures
• Space complexity in data structures
• Binary search algorithm in Java
• Merge sort in Java
• HashSet in Java

Conclusion

Time complexity in data structures is a way of predicting how an operation's work grows with its input. To find it, count iterations: loops multiply, sequences add, halving loops are logarithmic, and only the largest term survives. Check the cost of every library call inside a loop, because hidden loops are the most common source of unexpected O(n²) code. Choosing a structure whose frequent operations are O(1) or O(log n) is often the single biggest performance improvement you can make.