Java Big-O Notation

Big-O notation describes how the running time (or memory use) of an algorithm grows as the size of its input grows. It tells you the algorithm’s efficiency trend, not its exact speed in seconds.

Why It Matters

Two methods can produce the same correct result but scale very differently. A method that checks every element in a list of 10 items feels instant. The same method run on a list of 10 million items might take minutes. Big-O gives you a shorthand for predicting that kind of slowdown before it happens, so you can choose a better algorithm or data structure early.

Big-O focuses on the worst case and ignores constant factors like CPU speed. We write it using the input size n, such as O(n) or O(n^2).

Common Complexity Classes

Notation	Name	Example
O(1)	Constant	Accessing an array element by index
O(log n)	Logarithmic	Binary search on a sorted array
O(n)	Linear	Scanning every element once
O(n log n)	Linearithmic	Efficient sorting, like merge sort
O(n^2)	Quadratic	Comparing every element to every other element

Example: Linear Search

The method below searches an array for a target value by checking each element one at a time. In the worst case, it examines every element exactly once, so its time grows in direct proportion to n, the array’s length. This makes it O(n).

public class Main {
    public static void main(String[] args) {
        int[] numbers = {4, 8, 15, 16, 23, 42};
        int target = 23;

        int index = linearSearch(numbers, target);
        System.out.println("Found " + target + " at index " + index);
    }

    public static int linearSearch(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Output:
Found 23 at index 4

How It Works

The for loop runs at most numbers.length times. If the array doubles in size, the loop can run up to twice as many times in the worst case. That direct, one-to-one relationship between input size and work done is exactly what O(n) describes.

Compare this to accessing numbers[3] directly. That takes the same amount of time whether the array has 6 elements or 6 million, because array indexing doesn't depend on the array's size. That operation is O(1).

How to Estimate Big-O

• A single loop over n items is usually O(n).
• A loop nested inside another loop, each running roughly n times, is usually O(n^2).
• Code with no loops or recursion, just a fixed number of steps, is O(1).
• Repeatedly cutting the input in half, like binary search, is O(log n).

When a method has multiple steps in sequence, keep only the term that grows fastest as n increases — that dominant term is the method's Big-O.

Big-O gives you a fast way to compare algorithms before writing a single line of code. The next lesson looks at how different data structures affect the Big-O of common operations like insertion and lookup.