Time & Space Complexity (Big-O) Explained Simply (Java)

Lesson 1: Time & Space Complexity (Big-O)

Watch this lesson on our YouTube channel.

Chapters in this video

0:00 Intro
0:20 Why we need Big-O
0:51 Phone book example
1:30 3 simple rules
2:03 The Big-O ladder
2:45 How big does it get?
3:17 Spotting Big-O in Java code
3:48 Space complexity & the call stack
4:22 Amortized & average vs worst
4:59 Reading constraints
5:38 Quick quiz
6:05 Recap

In simple words

Big-O tells you how the work grows when the input grows. We don't measure seconds (they change from laptop to laptop). We count steps as the input size n becomes very large.

Two simple rules: drop constants (O(2n) is just O(n)) and keep only the biggest term (O(n² + n) is O(n²)). If there are two different inputs, use two letters: O(n · m).

Think of it like…
Finding a name in a phone book. Turning page by page is O(n). Opening the middle, then the middle of the correct half, and so on, is O(log n) — a 1,000-page book needs only about 10 openings.

Key ideas

O(1) constant — array index access, HashMap get. Same work for 10 or 10 million items.
O(log n) — you cut the problem in half every step (binary search, balanced tree).
O(n) — one pass over the data (one loop).
O(n log n) — good sorting (merge sort, Arrays.sort on objects).
O(n²) — a loop inside a loop over the same data.
O(2ⁿ) — trying every subset. O(n!) — trying every ordering (permutation).
Space complexity = extra memory you create: new arrays, maps, and the recursion call stack (depth counts!).
Amortized cost = average over many operations. ArrayList.add is O(1) amortized even though a resize sometimes costs O(n).
Best / average / worst case: interviews usually mean worst case unless you say otherwise (e.g. HashMap is O(1) average).

Operations & cost

Input size n (from constraints)	Complexity that will pass (~10⁸ steps/sec)
n ≤ 10	O(n!) — permutations
n ≤ 20	O(2ⁿ) — subsets / bitmask
n ≤ 500	O(n³)
n ≤ 10⁴	O(n²)
n ≤ 10⁶	O(n log n) or O(n)
n ≤ 10⁹ or more	O(log n) or O(1) — math / binary search

Java code

// O(1): one step no matter how big the array is
int first = arr[0];

// O(n): one loop
for (int x : arr) sum += x;

// O(n^2): loop inside a loop
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (arr[i] + arr[j] == target) return true;

// O(log n): the range halves every step
while (n > 1) { n = n / 2; steps++; }

// O(n) SPACE: extra array of size n
int[] copy = new int[n];

// Recursion: depth n  =>  O(n) stack space even with no arrays
int sumTo(int n) { return n == 0 ? 0 : n + sumTo(n - 1); }

Spot it when

The constraints line (like 1 ≤ n ≤ 10⁵) quietly tells you the expected complexity — use the table above.
n ≤ 10⁵ usually means O(n²) is too slow; aim for O(n log n) or O(n).

Interview tip

★ Finish every answer by saying the time and space complexity out loud — before the interviewer asks. It signals seniority.

Lesson 2: Java Toolkit for DSA →