Big-O Through Code Examples: Understanding Algorithm Complexity
1. Overview
Big-O is a way to describe how fast the runtime (or memory) grows as input size increases. This article doesn’t use dry math formulas; instead, it goes through each common complexity level with real Java code and analyzes which lines cause the cost. After reading, you’ll be able to look at a code snippet and instantly guess whether it’s O(1), O(n), O(n log n), or O(n²) without manual counting.
2. What is Big-O and Why Should You Care
Big-O answers the question: “If input doubles, how much does runtime increase?” It ignores constants and minor factors, keeping only the growth trend as n (input size) approaches infinity.
n = 1.000 -> O(n) runs ~1.000 steps
n = 1.000.000 -> O(n) runs ~1.000.000 steps (linear growth)
n = 1.000.000 -> O(n²) runs ~10^12 steps (exponential growth)Two pieces of code can “look the same at first glance” but have very different complexity if one has nested loops hidden inside a function call. Understanding Big-O helps you avoid writing code that runs fine with 100 test records but “freezes” in production with 10 million records.
Note: Big-O describes the worst case by the most common convention, unless explicitly stated as best-case or average-case.
3. O(1) – Constant Time
Runtime stays the same regardless of input size.
public class InventoryCache {
private final Map<String, Integer> stockBySku = new HashMap<>();
public Integer getStock(String sku) {
return stockBySku.get(sku); // HashMap.get is O(1) on average
}
}get() on HashMap computes the hash of the key and jumps directly to the corresponding bucket, independent of the number of elements in the map. Similarly, accessing array[i] or list.get(i) with ArrayList is also O(1) because it only needs to calculate the offset address.
4. O(n) – Linear Time
Runtime increases proportionally with input size.
public class OrderValidator {
public boolean hasExpiredItem(List<Order> orders) {
for (Order order : orders) {
if (order.isExpired()) {
return true; // stops early but worst-case still scans all
}
}
return false;
}
}The for loop goes through at most n elements of orders. Worst case happens when no order is expired, forcing you to check the entire list. This is the classic O(n) pattern: a single loop, not nested.
4.1. Common Trap: contains() in a Loop
public class DuplicateChecker {
// O(n²) because contains() on List is O(n), repeated n times
public boolean hasDuplicateSlow(List<String> emails) {
List<String> seen = new ArrayList<>();
for (String email : emails) {
if (seen.contains(email)) {
return true;
}
seen.add(email);
}
return false;
}
}seen.contains(email) on ArrayList is O(n) because it has to scan linearly to find it. Calling it inside the for loop turns the entire function into O(n²) — an easy mistake to make when you don’t pay attention to the underlying data structure.
public class DuplicateChecker {
// O(n) because HashSet.add/contains is O(1)
public boolean hasDuplicateFast(List<String> emails) {
Set<String> seen = new HashSet<>();
for (String email : emails) {
if (!seen.add(email)) { // add() returns false if it already exists
return true;
}
}
return false;
}
}Just by changing List to HashSet, complexity drops from O(n²) to O(n). This is the most practical example showing that choosing the right data structure matters more than “micro-optimizing”.
5. O(log n) – Logarithmic Time
Each step eliminates half of the search space.
public class PriceLookup {
// sortedPrices must be sorted in ascending order first
public int findIndex(int[] sortedPrices, int target) {
int low = 0;
int high = sortedPrices.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sortedPrices[mid] == target) {
return mid;
} else if (sortedPrices[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}Binary search halves the array at each while loop, so with n = 1.000.000 it takes only about 20 steps (log₂ 1.000.000 ≈ 20) to find the result, instead of scanning a million elements linearly.
class PriceLookupTest {
@Test
void shouldFindIndexInSortedArray() {
int[] prices = {10, 20, 30, 40, 50};
PriceLookup lookup = new PriceLookup();
int index = lookup.findIndex(prices, 40);
assertThat(index).isEqualTo(3);
}
@Test
void shouldReturnMinusOneWhenNotFound() {
PriceLookup lookup = new PriceLookup();
int index = lookup.findIndex(new int[] {1, 2, 3}, 99);
assertThat(index).isEqualTo(-1);
}
}This test verifies correct behavior both when found (returns index) and when not found (returns -1), the two most critical branches of binary search.
6. O(n log n) – Combining Linear and Logarithmic
This is the complexity of efficient sorting algorithms like merge sort, quick sort (average case), or Collections.sort().
public class RevenueReport {
public List<Order> sortByAmountDescending(List<Order> orders) {
List<Order> copy = new ArrayList<>(orders);
copy.sort(Comparator.comparing(Order::amount).reversed()); // O(n log n)
return copy;
}
}Collections.sort()/List.sort() in Java uses Timsort (a variant of merge sort), guaranteeing O(n log n) in the worst case. If you see code calling sort() inside a loop that runs n times, the total complexity multiplies to O(n² log n) — a sign you need to refactor.
7. O(n²) – Quadratic Time
Two nested loops, each running through all (or nearly all) of the input.
public class PairFinder {
// Find all pairs of products whose price sum equals target
public List<int[]> findPairsSlow(int[] prices, int target) {
List<int[]> result = new ArrayList<>();
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
if (prices[i] + prices[j] == target) {
result.add(new int[] {prices[i], prices[j]});
}
}
}
return result;
}
}Outer loop runs n times, inner loop runs up to n times for each outer iteration — total comparisons are roughly n²/2, so complexity is O(n²). With n = 10.000, that’s 50 million comparisons — it still runs but noticeably slower.
public class PairFinder {
// O(n) thanks to HashSet storing seen values
public List<int[]> findPairsFast(int[] prices, int target) {
List<int[]> result = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
for (int price : prices) {
int complement = target - price;
if (seen.contains(complement)) {
result.add(new int[] {complement, price});
}
seen.add(price);
}
return result;
}
}Instead of comparing every pair, we only need a single loop and O(1) lookups in HashSet. This is the common “trade time for space” technique: we use extra memory to store seen, but reduce complexity from O(n²) to O(n).
8. O(2^n) – Exponential Time
Runtime doubles every time input increases by 1 — commonly seen in recursive functions that compute all subsets.
public class SubsetGenerator {
public List<List<Integer>> generateAllSubsets(List<Integer> items) {
List<List<Integer>> result = new ArrayList<>();
backtrack(items, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(List<Integer> items, int index,
List<Integer> current, List<List<Integer>> result) {
if (index == items.size()) {
result.add(new ArrayList<>(current));
return;
}
// Branch 1: don't select item[index]
backtrack(items, index + 1, current, result);
// Branch 2: select item[index]
current.add(items.get(index));
backtrack(items, index + 1, current, result);
current.remove(current.size() - 1);
}
}Each element creates 2 recursive branches (select or don’t select), so with n elements we get 2^n subsets. With n = 20, that’s already over 1 million subsets; n = 40 won’t finish on any machine in reasonable time. This is a sign to consider dynamic programming if the problem allows it.
9. Quick Comparison with Real Benchmarks
A simple test example to “see” the difference between O(n) and O(n²):
class DuplicateCheckerBenchmarkTest {
@Test
void fastVersionShouldHandleLargeInputQuickly() {
List<String> emails = new ArrayList<>();
for (int i = 0; i < 100_000; i++) {
emails.add("user" + i + "@example.com");
}
DuplicateChecker checker = new DuplicateChecker();
long start = System.nanoTime();
boolean hasDuplicate = checker.hasDuplicateFast(emails);
long elapsedMs = (System.nanoTime() - start) / 1_000_000;
assertThat(hasDuplicate).isFalse();
assertThat(elapsedMs).isLessThan(500); // O(n) so still very fast with 100k elements
}
}If you try replacing hasDuplicateFast with hasDuplicateSlow for the same 100.000 emails, runtime will jump well beyond 500ms — visual proof of the difference between O(n) and O(n²) on real data.
10. Summary Table and Quick Recognition Rules
| Big-O | Signs in Code | Example |
|---|---|---|
| O(1) | No loop, direct access (array index, HashMap.get) | map.get(key) |
| O(log n) | Each step eliminates part of search space | Binary search |
| O(n) | Single loop through input | for loop through List |
| O(n log n) | Loop combined with sort, or divide-and-conquer | Collections.sort() |
| O(n²) | Loop nested in loop, both through input | Comparing every pair |
| O(2^n) | Recursion with 2 branches per step, no pruning | Generate all subsets |
Quick counting rule: count nested loops that iterate through input — each level adds one “power of n”. If the loop calls library functions (contains, sort, indexOf), look up their complexity before adding to the total.
Note: Big-O says nothing about real constants. An O(n) algorithm with a large constant (like reading a file each loop) can be slower than O(n log n) with a small constant when
nisn’t large enough. Don’t blindly optimize for Big-O without profiling real performance.
11. Conclusion
Big-O is a tool to predict trends, not absolute numbers — but those trends determine whether your code survives or crashes when data grows. Most practical tip: whenever you write a loop, ask yourself “does this loop call any O(n) function inside?” — that’s the source of most unwanted O(n²) bugs in practice. Mastering the 6 complexity levels above is enough to understand and critique most algorithm code you encounter daily.
HoanTien.proCashback on Shopee, TikTok Shop and Lazada (Vietnam)iOS · Android · Web
Binary search and variations: lower bound, rotated array, answer search
Implement binary search correctly on the first try and apply variations for lower/upper bound, rotated array, and answer search using Java 21.
HashMap Solutions for Counting Problems in Java
Use HashMap to count frequencies, find the most common element, count pairs, and group anagrams — with complexity and common pitfalls.
Two Pointers and Sliding Window: Optimizing Arrays and Strings
Learn two pointers and sliding window techniques to solve array/string problems with O(n) complexity, with runnable Java examples.