Stage 5: Data structures and algorithms, lesson 1 of 5

Big-O: how fast is your code?

Beginner3 min readall versions
Explain it forThe essentials plus production detail and pitfalls.

Big-O describes how running time (or memory) grows with the input size n, ignoring constants.

  • O(1), constant: an array index, HashMap.get.
  • O(log n): halves the problem each step, like binary search or a TreeMap lookup.
  • O(n): one pass, like finding the maximum or list.contains.
  • O(n log n): efficient sorting such as List.sort.
  • O(n²): nested loops over the same data, like comparing every pair.
  • O(2ⁿ): trying every subset, like naive recursive Fibonacci.

To estimate it, look at how loops nest, drop constants (O(2n) is O(n)) and keep the biggest term (O(n² + n) is O(n²)).

For a million items, O(n log n) is about 20 million steps (fast) while O(n²) is a trillion (hours). Picking the right data structure is often the whole optimisation.

Example

Java
// O(n²): compare every pair
static boolean hasDuplicateSlow(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

// O(n): one pass with a HashSet (O(1) average add and contains)
static boolean hasDuplicateFast(int[] a) {
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (!seen.add(x)) return true;        // add returns false if already present
    }
    return false;
}

// O(log n): binary search on sorted data
int[] sorted = {3, 8, 15, 23, 42, 57};
int index = Arrays.binarySearch(sorted, 23);   // 3

Common mistake

Calling list.contains or list.remove(Object) inside a loop. Each call is O(n), so the loop becomes O(n²); use a HashSet.

Under the hood

Big-O hides constants and memory effects: for small inputs an O(n) scan over an array often beats O(log n) lookups in a pointer-heavy tree, because CPUs love contiguous memory. Amortised cost matters too: ArrayList.add is O(1) amortised even though an occasional resize copies everything. In interviews, always state time and space complexity and the trade-off (the fast duplicate check uses O(n) extra memory).

Check yourself

Two nested loops over the same array of n items are typically…

How this connects

Part of Crack the Java interview.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.