Java Big-O Notation
Big-O notation is the language programmers use to describe how the running time or memory usage of an algorithm grows as the size of its input grows. Instead of measuring exact seconds, which depend on your CPU, JVM warm-up, and background processes, Big-O gives you a hardware-independent way to compare algorithms and predict how they will behave on inputs ten times, a hundred times, or a million times larger than the ones you tested. Every Java developer needs this vocabulary. It explains why an ArrayList.contains() call inside a loop can quietly turn a fast program into a slow one, and it is how you choose between an ArrayList, a HashMap, and a TreeMap for a given job.
Overview: How Big-O Notation Works
Big-O describes how the number of basic operations an algorithm performs grows relative to the size of its input, which is conventionally called n. If you double n, does the work stay the same, double, or quadruple? That question is what Big-O answers. We write this as a function of n, such as O(n) or O(n^2), where the letter O stands for "order of" — the order of magnitude of the growth rate.
Two simplifications make Big-O useful. First, we drop constant factors: an algorithm that does 3n operations and one that does 100n operations are both O(n), because what matters for large inputs is the shape of the growth curve, not the multiplier. Second, we drop lower-order terms: an algorithm that does n^2 + n + 1 operations is O(n^2), because as n grows very large, the n^2 term completely dominates the others. This is why Big-O is called asymptotic analysis — it describes behavior as n approaches infinity, not the exact operation count for a specific small input.
It helps to connect this to what actually happens when your Java code runs. Array access such as numbers[i] is O(1) because the JVM computes the memory address directly as baseAddress + i * elementSize — one arithmetic calculation regardless of array size. A for loop that visits every element once is O(n) because the JVM executes the loop body once per element, and each iteration involves fixed, constant work. Nested loops multiply: a loop inside a loop, each running roughly n times, produces O(n^2) because the inner loop’s body runs once for every iteration of the outer loop. Recursive calls are analyzed with recurrence relations — for example, binary search halves the problem on every call, which resolves to O(log n).
Worst Case, Average Case, and Best Case
Unless stated otherwise, Big-O in casual conversation almost always refers to the worst case — the maximum number of operations the algorithm could perform on the input that is hardest for it. For example, linear search’s worst case is O(n) because the target might be the last element or absent entirely, even though on average across many random inputs it might examine only half the array. Some data structures also have important gaps between average and worst case: a HashMap offers O(1) average-case lookups, but its true worst case is O(n) if every key collides into the same bucket. In practice Java’s hashing and bucket design make this rare, but it is worth knowing the difference exists.
Time Complexity vs. Space Complexity
Big-O is not only about time. Space complexity measures how much extra memory an algorithm needs as n grows, beyond the input itself. Sorting an array in place with a swap-based algorithm uses O(1) extra space, while an algorithm that builds a brand-new array or list of size n to hold intermediate results uses O(n) extra space. When you choose between algorithms, both dimensions matter: a faster algorithm that consumes far more memory is not automatically the better choice, especially in memory-constrained environments.
Syntax: Reading and Writing Big-O
Big-O expressions are written as O(f(n)), where f(n) is a function of the input size n. You will see it in library documentation, code review comments (// O(n log n)), and interview discussions. The table below lists the growth rates you will encounter constantly in everyday Java code, ordered from fastest to slowest.
| Notation | Name | Typical Java example |
|---|---|---|
O(1) |
Constant | Array index access, HashMap.get (average case), arithmetic |
O(log n) |
Logarithmic | Binary search, balanced tree lookup (TreeMap) |
O(n) |
Linear | Single loop over an array or ArrayList, ArrayList.contains |
O(n log n) |
Linearithmic | Collections.sort, Arrays.sort (comparison-based) |
O(n^2) |
Quadratic | Nested loops over the same input, bubble sort, selection sort |
O(2^n) |
Exponential | Naive recursive Fibonacci, generating all subsets |
O(n!) |
Factorial | Generating all permutations of n items |
Examples
Example 1: O(1) Access vs. O(n) Search
public class Main {
public static void main(String[] args) {
int[] numbers = {4, 8, 15, 16, 23, 42, 61, 99, 100, 7};
// O(1): constant time access by index
int direct = numbers[3];
System.out.println("Direct access numbers[3] = " + direct);
// O(n): linear search must scan until it finds the target
int target = 99;
int comparisons = 0;
int foundIndex = -1;
for (int i = 0; i < numbers.length; i++) {
comparisons++;
if (numbers[i] == target) {
foundIndex = i;
break;
}
}
System.out.println("Found " + target + " at index " + foundIndex + " after " + comparisons + " comparisons");
}
}
Output:
Direct access numbers[3] = 16
Found 99 at index 7 after 8 comparisons
Accessing numbers[3] takes exactly one step no matter how large the array is — that is O(1). Finding the value 99, however, requires checking elements one by one until a match is found. In the worst case (the value is last, or missing), the loop runs n times, which is O(n).
Example 2: O(n^2) Nested Loops
public class Main {
public static void main(String[] args) {
int[] data = {5, 2, 9, 1, 7, 3};
int n = data.length;
int comparisons = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
comparisons++;
if (data[i] > data[j]) {
// would swap here in a real bubble sort pass
}
}
}
System.out.println("Array size n = " + n);
System.out.println("Total comparisons = " + comparisons);
System.out.println("n*(n-1)/2 = " + (n * (n - 1) / 2));
}
}
Output:
Array size n = 6
Total comparisons = 15
n*(n-1)/2 = 15
The outer loop runs n times, and for each of those, the inner loop runs roughly n more times, giving approximately n * n = n^2 total comparisons. The exact count here, n(n-1)/2, still grows proportionally to n^2 once you drop the constant factor of one half and the lower-order term — this is exactly the pattern behind bubble sort and selection sort, both O(n^2) algorithms.
Example 3: O(log n) Binary Search
public class Main {
public static void main(String[] args) {
int[] sorted = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31};
int target = 23;
int steps = binarySearch(sorted, target);
System.out.println("Array size: " + sorted.length);
System.out.println("Steps to find " + target + ": " + steps);
}
static int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1, steps = 0;
while (low <= high) {
steps++;
int mid = (low + high) / 2;
if (arr[mid] == target) {
return steps;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return steps;
}
}
Output:
Array size: 16
Steps to find 23: 2
Binary search only works on sorted data, and it eliminates half of the remaining candidates on every step. For an array of 16 elements, the maximum possible number of steps is log2(16) = 4, and here the target is found in just 2. Compare this to linear search, which could take up to 16 comparisons on the same array — the gap between O(log n) and O(n) widens dramatically as n grows.
How It Works Step by Step: Analyzing Your Own Code
When you need to figure out the Big-O of a method you wrote, work through these rules:
- Sequential statements add. A block of code that does an
O(n)loop followed by a separateO(n)loop isO(n) + O(n) = O(2n), which simplifies toO(n)after dropping the constant. - Nested loops multiply. A loop of size
ncontaining another loop of sizenisO(n) * O(n) = O(n^2). If the inner loop’s size depends on the outer loop’s current position (as in Example 2), the total is stillO(n^2)because the number of comparisons is bounded byn^2. - The slowest term wins. A method that does an
O(n)pass and then anO(n^2)pass isO(n^2)overall, because that term dominates asngrows. - Recursion uses a recurrence relation. Binary search’s recursive form calls itself once on half the input, doing
O(1)work per call:T(n) = T(n/2) + O(1), which resolves toO(log n). A recursive function that calls itself twice on nearly the full input, like naive Fibonacci, resolves to exponential growth,O(2^n). - Know your library’s complexity. Calling a method whose own complexity is not
O(1)inside a loop silently multiplies your complexity — this is the single most common source of accidental quadratic code, covered next.
Common Mistakes
Mistake 1: Calling ArrayList.contains() Inside a Loop
ArrayList.contains() is O(n) because it scans the list linearly. Calling it inside another loop turns an innocent-looking piece of code into O(n * m), which behaves like O(n^2) when the two collections are similar in size.
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> listA = new ArrayList<>();
List<Integer> listB = new ArrayList<>();
for (int i = 0; i < 5000; i++) {
listA.add(i);
}
for (int i = 4000; i < 4010; i++) {
listB.add(i);
}
int matches = 0;
for (int value : listB) {
if (listA.contains(value)) { // O(n) search inside a loop -> O(n * m)
matches++;
}
}
System.out.println("Matches: " + matches);
}
}
Output:
Matches: 10
This works correctly, but for every one of the 10 elements in listB it may scan up to 5000 elements of listA. The fix is to use a HashSet, whose contains() is O(1) on average, turning the whole operation into O(n + m):
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Set<Integer> setA = new HashSet<>();
List<Integer> listB = new ArrayList<>();
for (int i = 0; i < 5000; i++) {
setA.add(i);
}
for (int i = 4000; i < 4010; i++) {
listB.add(i);
}
int matches = 0;
for (int value : listB) {
if (setA.contains(value)) { // O(1) average lookup -> overall O(n + m)
matches++;
}
}
System.out.println("Matches: " + matches);
}
}
Output:
Matches: 10
Mistake 2: String Concatenation in a Loop
Java String objects are immutable, so every use of += on a String inside a loop creates a brand-new String and copies all the previous characters into it. A loop that concatenates n times therefore does 1 + 2 + 3 + ... + n character copies, which is O(n^2), not the O(n) a reader might assume.
String result = "";
for (int i = 0; i < 5; i++) {
result += i; // creates a new String object every iteration -> O(n^2) overall
}
System.out.println(result);
Output:
01234
The fix is StringBuilder, which maintains a mutable, resizable character buffer and appends in amortized O(1) time per call, making the whole loop O(n):
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 5; i++) {
sb.append(i); // appends into the existing buffer -> O(n) overall
}
System.out.println(sb.toString());
Output:
01234
Best Practices
- Identify the Big-O of your algorithm before micro-optimizing constants — an
O(n^2)algorithm with a "fast" inner loop still loses to anO(n log n)algorithm oncenis large enough. - Learn the complexity of the standard library methods you use most:
ArrayList.getisO(1),ArrayList.containsisO(n),LinkedList.get(index)isO(n), andHashMap/HashSetoperations areO(1)average butO(log n)forTreeMap/TreeSet. - Watch for method calls inside loops — that is where accidental quadratic behavior almost always hides.
- Use
StringBuilderfor building strings incrementally instead of repeated+=concatenation. - Consider both time and space complexity; an algorithm that trades memory for speed (like using a
HashSetto avoid repeated scans) is often the right trade in practice. - Test performance-sensitive code on realistically large inputs, not just small samples where an
O(n^2)bug is invisible. - Remember that Big-O describes trends, not exact timings — always profile before assuming which of two similarly-scaled algorithms is faster in your real environment.
Practice Exercises
- Exercise 1: Write a Java method
sum(int[] arr)that adds up all the elements of an array using a single loop. State its Big-O time complexity and explain why in one sentence. - Exercise 2: Given a method with two separate (not nested) loops that each run
ntimes over the same array, what is the overall Big-O? Now change one of the loops to be nested inside the other and state the new Big-O. - Exercise 3: The following method checks whether an array contains any duplicate values by comparing every pair of elements, making it
O(n^2). Rewrite it using aHashSetso that it runs inO(n):boolean hasDuplicates(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] == arr[j]) return true; } } return false; }
Summary
- Big-O notation describes how an algorithm’s time or space requirements grow as the input size
ngrows, ignoring constant factors and lower-order terms. - Common classes, from fastest to slowest, are
O(1),O(log n),O(n),O(n log n),O(n^2),O(2^n), andO(n!). - Sequential code blocks add their complexities; nested loops multiply theirs; the largest term dominates the total.
- Recursive algorithms are analyzed with recurrence relations — halving the problem each call leads to
O(log n). - Big-O usually refers to worst-case behavior, though average case matters too, especially for hash-based collections.
- Calling an
O(n)library method (likeArrayList.contains) inside a loop is the most common way quadratic complexity sneaks into real code. - String concatenation with
+=in a loop isO(n^2); useStringBuilderforO(n)string building. - Knowing Big-O lets you predict how your program will scale before it becomes a production problem.
