BackendBench
Coffee

Unravel › Java concepts › Algorithms and data structures

Java language

Time complexity (Big O)

Big O describes how the running time grows with the input size n.

🔎 Unravel this example

At a glance

Mental model

Looking for a name: reading every page of the phone book is O(n); opening it in the middle and halving the search is O(log n); asking everybody in town to compare themselves with everybody else is O(n²).

What happens, in order
  1. 1Count how many times the innermost statement runs as n grows: one loop is about n, two nested loops over the same data are about n × n
  2. 2Common classes, best to worst: O(1) constant (array index, HashMap.get), O(log n) (binary search, TreeMap.get), O(n) (one pass, ArrayList.contains), O(n log n) (good sorting), O(n²) (nested loops, bubble sort), O(2ⁿ) (naive subsets or recursion)
  3. 3Drop constants and smaller terms: 3n² + 5n + 2 is O(n²)Big O is the shape of the growth, not the exact time.
  4. 4Hidden costs: list.contains and list.remove(0) inside a loop make it O(n²); string += in a loop copies the string every time; list.get(i) on a LinkedList is O(n)
Remember
Watch out
Nested loops over large lists when a map lookup would doCalling an O(n) method such as list.contains or String.length() on a LinkedList inside a loopOptimising constant factors instead of the growth rate
Example (highlighted lines explain it)
import java.util.*;public class Pairs {  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;  }  static boolean hasDuplicateFast(int[] a) {    Set<Integer> seen = new HashSet<>();    for (int v : a) if (!seen.add(v)) return true;    return false;  }}
Read the full explanation (about 2 min)

Big O describes how the running time grows with the input size n. One loop over n items is O(n); a loop inside a loop is O(n²); halving the problem each step is O(log n). It tells you whether code will still be fast with 1,000,000 items.

A mental model

Looking for a name: reading every page of the phone book is O(n); opening it in the middle and halving the search is O(log n); asking everybody in town to compare themselves with everybody else is O(n²).

How it works

Count how many times the innermost statement runs as n grows: one loop is about n, two nested loops over the same data are about n × n.

Common classes, best to worst: O(1) constant (array index, HashMap.get), O(log n) (binary search, TreeMap.get), O(n) (one pass, ArrayList.contains), O(n log n) (good sorting), O(n²) (nested loops, bubble sort), O(2ⁿ) (naive subsets or recursion).

Drop constants and smaller terms: 3n² + 5n + 2 is O(n²). Big O is the shape of the growth, not the exact time.

Hidden costs: list.contains and list.remove(0) inside a loop make it O(n²); string += in a loop copies the string every time; list.get(i) on a LinkedList is O(n).

Going deeper

Fixes for O(n²): put values in a HashSet or HashMap for O(1) lookups, sort first and use two pointers or binary search, or precompute (prefix sums).

Space matters too: a hash map for speed costs O(n) memory. Also consider amortised cost: ArrayList.add is O(1) on average even though occasional growth copies everything.

For small n, a simple O(n²) code can beat a clever O(n log n) one; measure before optimising. For n of a million, O(n²) means 10¹² steps and will not finish.

Under the hood

Real time = steps × cost per step, and per-step cost depends on cache behaviour, allocation and I/O. Big O ignores those, so it predicts the trend, not the stopwatch result.

Common mistakes

  • Nested loops over large lists when a map lookup would do.
  • Calling an O(n) method such as list.contains or String.length() on a LinkedList inside a loop.
  • Optimising constant factors instead of the growth rate.

How Unravel recognises it

When you paste code, Unravel looks for these signs of time complexity (big o). Spotting them yourself is a good habit when you read unfamiliar code:

Part of a learning path

Related concepts

Sets: HashSet, LinkedHashSet, EnumSetJava languageHow HashMap worksJava languageSorting algorithmsJava languageMeasuring performance and JMHJava language

Frequently asked questions

What is Time complexity (Big O)?

Big O describes how the running time grows with the input size n. One loop over n items is O(n); a loop inside a loop is O(n²); halving the problem each step is O(log n). It tells you whether code will still be fast with 1,000,000 items.

What are the most common mistakes with Time complexity (Big O)?

Nested loops over large lists when a map lookup would do. Calling an O(n) method such as list.contains or String.length() on a LinkedList inside a loop. Optimising constant factors instead of the growth rate.

How can I see Time complexity (Big O) in real code?

Paste your own Java into Unravel and it will point out where time complexity (big o) appears, explain how it works at the detail level you choose, and draw the flow of the code around it.