Foundations

Big O Complexity

How to read it, how to derive it from code, and how Java's built-in collections perform across every operation you care about.

Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.

Section One · Foundation

What Big O Measures

Big O notation describes the growth rate of an algorithm’s resource usage — time or space — as a function of its input size n. It does not measure wall-clock time in milliseconds, because that depends on hardware, language, and compiler. It measures the rate of growth: if you double the input, does the algorithm take twice as long, four times as long, or the same amount of time? That growth rate is what determines whether an algorithm scales or breaks under real-world load.

Big O describes the upper bound — the worst the algorithm can do on any input of size n. This is deliberately pessimistic: an algorithm that runs in O(n) time might finish much faster on a sorted input, but the guarantee is that it will never be worse than linear. When comparing algorithms, upper bounds are more useful than averages because they tell you the worst case you will ever experience in production.

If I double the input size

▶

Does the runtime double (O(n)), stay the same (O(1)), or quadruple (O(n²))?

If I have 1 million records

▶

Will this algorithm finish in milliseconds, minutes, or never?

If I choose this data structure

▶

Which operations become cheap and which become expensive?

Constants and lower-order terms are dropped:

O(3n + 100) simplifies to O(n). O(n² + n) simplifies to O(n²).
Big O cares only about the dominant term as n grows large — constants and smaller terms become irrelevant at scale.

Section Two · Notation

Reading Big O Notation

O(1) Constant

The operation takes the same number of steps regardless of input size.

Java

 // O(1) — index formula, no loop int first = array[0]; // always 1 operation
map.get("key"); // hash lookup — 1 operation
deque.peekFirst(); // head pointer read — 1 operation 

O(1) does not mean fast:

O(1) means the time does not grow with input size — it could still be slow in absolute terms.
A HashMap.get() is O(1) but performs a hash computation, an array index, and possibly an equals() check — it is always the same cost regardless of map size.

O(log n) Logarithmic

The problem is halved at each step, so doubling the input adds only one more step.

Java

 // O(log n) — input halved each iteration int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids integer overflow if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
// Binary search — 1M elements needs only ~20 comparisons 

log₂(1,000,000) ≈ 20:

A sorted array of one million elements needs at most 20 comparisons with binary search.
That is why O(log n) is called “essentially constant” at practical scales — TreeMap.get() on a map with a billion keys still finishes in ~30 comparisons.

O(n) Linear

The number of steps grows in direct proportion to the input size.

Java

 // O(n) — visits every element once for (int x : list) {
    sum += x; // one operation per element
}
list.contains(target); // O(n) — scans from index 0
Collections.reverse(list);// O(n) — touches every element 

O(n) is the best you can do for unsorted data:

If the data is unsorted and you need to find an element, you must look at every element in the worst case — O(n) is optimal.
Any claim of faster-than-linear search on unsorted data requires either preprocessing (sorting, hashing) or a structural guarantee.

O(n log n) Linearithmic

Appears in efficient sorting algorithms — slightly worse than linear but dramatically better than quadratic.

Java

 // O(n log n) — divide and conquer sorting
Collections.sort(list); // merge sort internally
Arrays.sort(objectArray); // tim sort internally
Arrays.sort(primitiveArray); // dual-pivot quicksort — O(n log n) avg 

O(n log n) is the lower bound for comparison sorting:

Any algorithm that sorts by comparing elements cannot do better than O(n log n) — this is a mathematical proof, not a limitation of existing implementations.
The only way to sort faster is to use non-comparison methods like counting sort or radix sort, which require constraints on the input values.

O(n²) Quadratic

A nested loop where each element is compared to every other element — doubles the input, quadruples the runtime.

Java

 // O(n²) — nested loops, n × n iterations for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// n² total operations if (arr[i] + arr[j] == target) ...
    }
}
// 1,000 elements → 1,000,000 operations // 10,000 elements → 100,000,000 operations 

O(n²) is the threshold — avoid it for n > 10,000:

At n=10,000 a quadratic algorithm performs 100 million operations.
At n=100,000 it performs 10 billion — seconds become minutes.
Whenever you see a nested loop over the same collection, ask whether a HashMap can reduce the inner loop to O(1).

O(2ⁿ) Exponential

Each additional input element doubles the total work — grows faster than any polynomial, unusable for n > 30.

Java

 // O(2ⁿ) — naive recursive fibonacci int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2); // each call spawns two more
}
// fib(30) → ~1 billion calls // fib(50) → ~1 quadrillion calls — never finishes 

Memoization converts O(2ⁿ) to O(n):

Storing previously computed results eliminates redundant recursive calls. fib(n) with a cache (dynamic programming) runs in O(n) time and O(n) space — the same answer, exponentially faster.
Recognising exponential growth is the first step to knowing when dynamic programming applies.

Complexity at Scale

Notation	Name	n=10	n=100	n=1,000	n=1,000,000
O(1)	Constant	1	1	1	1
O(log n)	Logarithmic	3	7	10	20
O(n)	Linear	10	100	1,000	1,000,000
O(n log n)	Linearithmic	33	664	9,966	19,931,568
O(n²)	Quadratic	100	10,000	1,000,000	10¹² (unusable)
O(2ⁿ)	Exponential	1,024	10³⁰ (∞)	∞	∞

═══════════════════════════════════════════════════════════════════════ -->

Section Three · Derivation

Deriving Complexity From Code

Reading Big O from existing analysis is one skill; deriving it from code you are looking at is another. The rules are mechanical — you do not need to count every operation, only identify the dominant pattern. Four patterns cover 95% of what you will encounter.

Rule 1 — Single Loop

A loop that runs n times contributes O(n) to the overall complexity.

Java

 // Each loop body runs exactly n times → O(n) for (int i = 0; i < n; i++) {
process(arr[i]); // O(1) work per iteration
}
// Total: n × O(1) = O(n) // Regardless of what is inside — as long as it is O(1): for (String s : list) {
    map.put(s, map.getOrDefault(s, 0) + 1); // O(1) HashMap ops
}
// Still O(n) — the loop count dominates 

The loop body must be O(1):

If the loop body itself is O(n) — for example, calling list.contains() inside a for loop — the total becomes O(n) × O(n) = O(n²).
Always analyse the body before multiplying.

Rule 2 — Nested Loops

Two nested loops over the same collection multiply their iterations — n × n = n².

Java

 // Outer loop: n iterations for (int i = 0; i < n; i++) {
// Inner loop: n iterations for each outer → n × n total for (int j = 0; j < n; j++) {
process(arr[i], arr[j]); // O(n²) total
}
}
// Different sizes: O(n × m) for (String a : listA) { // n iterations for (String b : listB) { // m iterations if (a.equals(b)) ... // O(n × m) total
}
}

HashMap breaks the inner loop:

If the inner loop is searching for a match, a HashMap built in O(n) reduces the inner search to O(1), converting the entire algorithm from O(n²) to O(n).
This is the most common optimisation pattern in array interview problems.

Rule 3 — Input Halved Each Step

When the active portion of the input is halved at each step, the total number of steps is proportional to log₂(n).

Java

 // Input halved each iteration → O(log n) int lo = 0, hi = n - 1;
while (lo <= hi) { // runs log₂(n) times int mid = lo + (hi - lo) / 2;
if (check(mid)) hi = mid - 1;
else lo = mid + 1;
}
// Tree traversal with height h = log n (balanced tree):
TreeNode cur = root;
while (cur != null) { // h = log n levels if (target < cur.val) cur = cur.left;
else if (target > cur.val) cur = cur.right;
else return cur;
}
// O(log n) — each step eliminates half the remaining nodes 

Halving is the signature of O(log n):

Any time you see a loop where the search space is cut in half — whether by lo/hi pointers, a balanced tree, or a divide-and-conquer recursion — the loop runs at most log₂(n) times.
Identify the shrinking variable to confirm.

Rule 4 — Recursive Calls

A recursive function’s complexity is the work per call multiplied by the total number of calls.

Java

 // Each call does O(1) work and makes 1 recursive call → O(n) int sum(int[] arr, int i) {
if (i == arr.length) return 0; // base case return arr[i] + sum(arr, i + 1); // 1 call, O(1) work → O(n)
}
// Each call does O(1) work and makes 2 recursive calls → O(2ⁿ) int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // 2 calls → exponential tree
}
// Divide and conquer: 2 calls on n/2 input + O(n) merge → O(n log n) void mergeSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(arr, lo, mid); // T(n/2) mergeSort(arr, mid+1, hi); // T(n/2) merge(arr, lo, mid, hi); // O(n)
}
// T(n) = 2T(n/2) + O(n) → O(n log n) by Master Theorem 

Draw the recursion tree to count calls:

For any recursive function, draw a tree where each node is one call and each branch is a recursive invocation.
The total number of nodes is the total number of calls.
Multiply by the work per call (excluding recursion) to get the total complexity.

The 3-step derivation process

Section Four · Cases

Best, Average, and Worst Case

Big O typically describes worst-case — the maximum number of steps on any input of size n. But algorithms can behave very differently depending on the input, so three cases matter: best, average, and worst. Understanding all three prevents false confidence from benchmarks on lucky inputs.

Best Case — Ω (Omega)

The ideal input

The input that makes the algorithm finish as fast as possible. Useful as a lower bound but rarely the number you plan for.

Linear search finds target at index 0 → Ω(1)
QuickSort with perfect median pivot → Ω(n log n)

Worst Case — O (Big O)

The hardest input

The input that forces the maximum number of steps. This is what Big O describes. Plan for this — production systems encounter worst-case inputs regularly.

Linear search: target not in array → O(n)
QuickSort: always picking smallest pivot → O(n²)

Average Case — Θ (Theta)

The expected input

The expected behaviour over all possible inputs of size n, weighted by probability. Harder to derive but most representative of real-world performance.

HashMap lookup: O(1) average, O(n) worst (all keys collide)
QuickSort: O(n log n) average with random pivot selection

Linear Search — three cases on the same array

Common Mistake: Assuming QuickSort is always O(n log n) because that is what the textbook says. QuickSort degrades to O(n²) when the pivot is consistently the smallest or largest element — exactly what happens on sorted or reverse-sorted input with a naive first-element pivot. Java’s Arrays.sort() for primitives uses dual-pivot QuickSort with safeguards; for objects it uses TimSort, which is O(n log n) worst case.

Section Five · Space

Space Complexity

Time complexity measures how runtime grows with input size — space complexity measures how memory usage grows. The two are often in tension: using extra memory (a HashMap, a cache, a second array) frequently reduces time complexity, and the trade-off is worth making explicit. When someone says an algorithm runs in O(1) space, they mean it uses a constant amount of extra memory regardless of input size — not that it uses zero memory.

Input space (the data itself)

▶

Not counted in space complexity — it is already there

Auxiliary space (extra memory the algorithm allocates)

▶

This is what space complexity measures

Recursive call stack

▶

Each frame uses memory — O(n) recursion depth = O(n) space

O(1) space (“in-place”)

▶

Algorithm uses only a fixed number of extra variables — no arrays, no maps, no stack frames proportional to n

Space Complexity Examples

Algorithm	Time	Space	Notes
Array reversal (in-place)	O(n)	O(1)	Swap with two pointers
Array reversal (new array)	O(n)	O(n)	Allocates n-element copy
Recursive fibonacci	O(2ⁿ)	O(n)	n stack frames at deepest path
Memoized fibonacci	O(n)	O(n)	Cache stores n results
Iterative fibonacci	O(n)	O(1)	Two variables, no cache
BFS on a graph	O(V+E)	O(V)	Queue holds up to V nodes
Merge sort	O(n log n)	O(n)	Merge step needs temp array
QuickSort (in-place)	O(n log n)	O(log n)	Stack frames = tree height

The time-space trade-off is always explicit:

When you add a HashMap to reduce O(n²) to O(n), you are trading O(n) space for O(n) time savings.
Name the trade-off when you make it — in code comments, in interviews, and in design discussions.

Section Six · Amortized

Amortized Analysis

Amortized analysis describes the average cost of an operation over a sequence of operations — not the worst single case, but the cost spread across many calls. It matters because some operations are occasionally expensive but cheaply distributed over time. ArrayList’s add() is the canonical example: most appends are O(1), but one in every n appends triggers a resize that costs O(n) — yet the average cost per append over n operations is still O(1).

Start with capacity 1. Each time the array fills, double it and copy all elements. Track the total copy operations across 16 appends.

ArrayList Resize Walkthrough

Append #	Capacity before	Resize?	Copy cost	Running total
1	1	No	0	0
2	1	Yes → 2	1	1
3	2	Yes → 4	2	3
4	4	No	0	3
5	4	Yes → 8	4	7
6–8	8	No	0	7
9	8	Yes → 16	8	15
10–16	16	No	0	15
Average copy cost per append: 15/16 ≈ 1 → O(1) amortized

Geometric series — resize cost halves each time we look back

Amortized ≠ average case:

Amortized O(1) means the total cost of n operations is O(n), so each individual operation costs O(1) on average — but some individual calls may be O(n).
Average case is about input distribution; amortized is about spreading one expensive operation across many cheap ones.

Section Seven · Reference

Java Collections Cheatsheet

Every Java collection has a defined complexity for its core operations — knowing these cold is the difference between a confident interview answer and an uncertain guess. This is the reference to bookmark: the complete complexity profile of every collection you will reach for.

List Implementations

Operation	ArrayList	LinkedList	Notes
`get(index)`	O(1)	O(n)	LinkedList must traverse from head/tail
`add()` at end	O(1)*	O(1)	*ArrayList amortized; LinkedList has tail ref
`add(i, val)`	O(n)	O(n)	ArrayList: shift; LinkedList: traverse to i
`remove(index)`	O(n)	O(n)	ArrayList: shift; LinkedList: traverse to i
`contains()`	O(n)	O(n)	Linear scan in both
`size()`	O(1)	O(1)	Both store as field
`iterator.next()`	O(1)	O(1)	ArrayList: index++; LinkedList: pointer follow

* LinkedList.get(i) is O(n) — never call it in a loop

Queue / Deque / Stack

Operation	ArrayDeque	LinkedList	PriorityQueue	Notes
`addFirst / push`	O(1)	O(1)	—	ArrayDeque: array index
`addLast / offer`	O(1)	O(1)	O(log n)	PQ: heap sift-up
`removeFirst / pop`	O(1)	O(1)	O(log n)	PQ: heap sift-down
`peekFirst`	O(1)	O(1)	O(1)	PQ: root is always min/max
`size`	O(1)	O(1)	O(1)	All store as field

Map Implementations

Operation	HashMap	LinkedHashMap	TreeMap	Notes
`get(key)`	O(1)*	O(1)*	O(log n)	*avg — O(n) worst (all collide)
`put(key, val)`	O(1)*	O(1)*	O(log n)	TreeMap maintains sorted order
`remove(key)`	O(1)*	O(1)*	O(log n)	—
`containsKey`	O(1)*	O(1)*	O(log n)	—
iteration	O(n)	O(n)	O(n)	LinkedHashMap: insertion order
`firstKey / lastKey`	—	—	O(log n)	TreeMap only — BST min/max

* HashMap O(1) average assumes a good hash function

Set Implementations

Operation	HashSet	LinkedHashSet	TreeSet	Notes
`add(value)`	O(1)*	O(1)*	O(log n)	—
`contains()`	O(1)*	O(1)*	O(log n)	—
`remove()`	O(1)*	O(1)*	O(log n)	—
`first() / last()`	—	—	O(log n)	TreeSet only
iteration	O(n)	O(n)	O(n)	TreeSet: sorted order

When in doubt: HashMap for lookup, ArrayDeque for LIFO/FIFO.:

HashMap gives O(1) get/put for the most common need — checking membership or counting frequency.
ArrayDeque gives O(1) push/pop/enqueue/dequeue for the second most common need — processing items in order.

LearningTree

Big O Complexity | Java DSA Guide

Big O Complexity

What Big O Measures

Reading Big O Notation

Deriving Complexity From Code

Best, Average, and Worst Case

The ideal input

The hardest input

The expected input

Space Complexity

Amortized Analysis

Java Collections Cheatsheet