Big-O & Complexity
Count how the work grows, not how long it takes — then you can predict "too slow" before writing a line.
▶ guided lesson⚡ 1-minute summary↻ 14 recall cards
before this: Mindset
01 · why it exists
Why this exists, and the weight it carries
since1894 · 1909 · 1976
Big-O notation (with Ω and Θ)
Paul Bachmann, Edmund Landau, Donald E. Knuth
Big-O came from number theory, not computing. Paul Bachmann used O in his 1894 book on analytic number theory; Edmund Landau spread it through his 1909 handbook on primes, and added little-o. In 1976 Donald Knuth saw people using O for lower bounds, where it doesn't fit. In "Big Omicron and big Omega and big Theta" (SIGACT News) he proposed Ω for "order at least" and Θ for "order exactly" — the notation algorithm analysis uses today.
the problem it solvedComparing algorithms without depending on the computer, the language or the compiler — only on how the work grows.
its jobs today
- Library contracts: Java's API docs promise costs, e.g. constant-time
get/putforHashMap(with a good hash) and guaranteed log(n) forTreeMap. - Design reviews: "this is O(n²) in the number of users" is a red flag before any code ships.
- Interviews: every solution is judged by its time and space complexity, said with a reason.
the weight it carries
Illustrative, at ~10⁸ simple steps per second and n = 10⁶: O(n log n) ≈ 2·10⁷ steps ≈ 0.2 s, while O(n²) = 10¹² steps ≈ 10⁴ s ≈ 2.8 hours. Same data, same machine — the growth rate alone decides.
without it
You'd only learn an algorithm is too slow after running it on real data — usually in production, on the biggest input.
when · why · how
- when
- Every time you compare two approaches, and every time you read the constraints.
- why
- It predicts "too slow" before you write code: at n = 10⁶, O(n) is 10⁶ steps and O(n²) is 10¹².
- how
- Find the innermost repeated operation, multiply nested loop sizes, add phases, keep the biggest term. Know library costs:
ArrayList.getO(1),TreeMap.getO(log n),List.containsO(n).
since1965
Time complexity & the input-size budget
Juris Hartmanis & Richard E. Stearns
In "On the computational complexity of algorithms" (1965), Hartmanis and Stearns classified computations by how the number of steps grows with the length of the input. That paper founded computational complexity theory, and won them the 1993 ACM Turing Award. The input-size table that competitive programmers memorise (n ≤ 20 → 2ⁿ, n ≤ 10⁵ → n log n) is the same idea applied to a one-second time limit.
the problem it solvedSaying precisely what "fast" means: running time as a function of input size n, so algorithms can be ranked and budgeted.
its jobs today
- Reading constraints: n ≤ 10⁵ tells you O(n²) is out before you design anything.
- Choosing data structures: O(1) average
HashMapvs O(log n)TreeMapvs an O(n) list scan. - Spotting hidden costs:
substring,containsandremove(0)inside a loop.
the weight it carries
Illustrative, ~10⁸ simple steps per second: n = 20 → 2ⁿ = 1,048,576 steps (fine); n = 10⁴ → n² = 10⁸ (about a second, borderline); n = 10⁶ → n log₂ n ≈ 2·10⁷ (fine) but n² = 10¹² (hours).
without it
You'd design an O(n²) answer for n = 10⁵, code it for 20 minutes, and get Time Limit Exceeded on the hidden tests.
when · why · how
- when
- The moment you read the constraints — before you pick an idea.
- why
- The budget names the target class: for n = 10⁵ only O(n log n) or O(n) fits, so you stop chasing O(n²) ideas early.
- how
- Plug the maximum n into each candidate: 10⁵ × 17 ≈ 1.7·10⁶ fits; (10⁵)² = 10¹⁰ doesn't. Unsure? Count steps in a
longcounter on a test input.
since1985
Amortized analysis
Robert E. Tarjan
Some operations are usually cheap but now and then very expensive — like a dynamic array that must copy everything when it fills up.
Charging every operation its worst case makes them look terrible.
In "Amortized Computational Complexity" (SIAM, 1985), Tarjan drew recent work by several researchers into one framework: average the cost over a whole sequence of operations — a guarantee, with no probability involved.
That's how we can honestly say ArrayList.add is O(1).
the problem it solvedGiving a fair, guaranteed cost to data structures whose rare expensive steps are paid for by many cheap ones.
its jobs today
- Growable collections:
ArrayList,StringBuilder,ArrayDequeandHashMapresize by a factor, so their adds are amortized O(1). - Pointer sweeps: in two pointers and sliding windows a pointer only moves forward, so a nested loop still does O(n) total work.
- Monotonic stacks: each element is pushed and popped at most once, so n operations cost O(n).
the weight it carries
Illustrative: 10⁶ adds into an array that doubles from capacity 1. The copies are 1 + 2 + 4 + … + 2¹⁹ = 2²⁰ − 1 = 1,048,575 moves, plus 10⁶ writes ≈ 2.05·10⁶ in total — about 2 per add. Growing by a fixed +10 instead would copy about (10⁶)² / 20 = 5·10¹⁰ elements.
without it
Every growable collection would look O(n) per add; you'd pre-size everything by hand or avoid the right structure out of fear.
when · why · how
- when
- An operation is occasionally expensive but runs many times: appends, resizes, pointer sweeps.
- why
- What your program pays is the total over n operations. Geometric growth makes n appends O(n) total → O(1) amortized each, at the price of some unused capacity.
- how
ArrayList.addandStringBuilder.appendare already amortized O(1). If you know the final size,new ArrayList<>(n)skips regrowth entirely.
02 · plain english
The idea in 30 seconds
Big-O describes how the number of steps grows as the input gets bigger — ignoring constants and small terms.
One loop over n items → O(n). A loop inside a loop → O(n²). Halving each step → O(log n).
Space complexity is the same idea for memory: extra arrays, maps, and the recursion stack all count.
picture this
Finding "Priya" in 2,000 phone contacts: scrolling from the top checks up to 2,000 names — O(n). Jumping to the middle of the sorted list and halving each time needs about 11 checks — O(log n). Hunting duplicate contacts by comparing every pair needs about 20 lakh checks — O(n²).
03 · remember
What you must know
- Count the dominant work, drop constants: 3n + 5 → O(n); n² + 100n → O(n²). Big-O is about the shape of growth, not exact time.
- Loop shapes: sequential loops add (O(n + m)); nested loops multiply (O(n·m)); a loop that halves or doubles is O(log n).
- log n is tiny: log₂ of a million is ~20, of a billion ~30. It counts how many times you can halve n before reaching 1.
- Best / average / worst: quote the worst case unless you say otherwise. HashMap is O(1) average; quicksort is O(n log n) average but O(n²) worst.
- Amortized O(1): an operation that is occasionally expensive but cheap on average over a long sequence — ArrayList
addcopies on growth, yet n adds cost O(n) total. - Space counts the recursion stack: recursing n levels deep uses O(n) memory even with no arrays. Halving recursion uses O(log n).
- Constraints → target complexity: n ≤ 10 → n!, ≤ 20 → 2ⁿ, ≤ 500 → n³, ≤ ~5,000 → n² (10⁴ is borderline), ≤ 10⁶ → n log n, ≤ 10⁸ → n (assuming ~10⁸ simple steps per second).
- Library calls aren't free:
list.contains,list.remove(0),substringand+=on strings are all O(n) — inside a loop they make O(n²).
04 · see it
Play with it in 3D
Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.
Growth race
Grow n one step at a time. To scale, the exponential bar makes everything else look flat.
Which complexity fits which n? (3D)
Height = digits in the step count. The green staircase is the input-size table every competitive programmer memorises.
What log n means
Keep halving until one item is left. Doubling n adds only one step.
Amortized O(1): a doubling array
Red bars are the rare expensive adds. Watch the average cost settle below 3.
Recursion costs space
Every waiting call is a stack frame. Peak depth = space complexity.
05 · cost
Time & space, explained
| n = 10³ | n = 10⁶ | Typical source | why | |
|---|---|---|---|---|
| O(1) | 1 | 1 | array index, HashMap get (average) | Work doesn't depend on n at all. |
| O(log n) | ~10 | ~20 | binary search, balanced tree, heap push/pop | Each step halves what's left: log₂ 10⁶ ≈ 20. |
| O(n) | 10³ | 10⁶ | one pass, two pointers, sliding window | Constant work per element. |
| O(n log n) | ~10⁴ | ~2·10⁷ | sorting, n heap operations | n elements × log n work each. |
| O(n²) | 10⁶ | 10¹² | all pairs, nested loops | n choices × n choices; at 10⁶ that's hours, not seconds. |
| O(2ⁿ) | ~10³⁰¹ | — | all subsets, naive recursion | Each element doubles the work: in or out. |
| O(n!) | ~10²⁵⁶⁷ | — | all permutations | n choices, then n−1, then n−2… |
| Max n | Allowed | Typical idea | why | |
|---|---|---|---|---|
| Tiny | ≤ 10 | O(n!) | try every permutation | 10! ≈ 3.6·10⁶ — fine. |
| Small | ≤ 20 | O(2ⁿ) | subsets, bitmask DP | 2²⁰ ≈ 10⁶ — fine; 2⁴⁰ is not. |
| Medium-small | ≤ 500 | O(n³) | triple loops, Floyd–Warshall, interval DP | 500³ = 1.25·10⁸ — borderline but usually OK. |
| Medium | ≤ ~5,000 (10⁴ borderline) | O(n²) | all pairs, 2D DP | (10⁴)² = 10⁸ ≈ a second: borderline. ~5,000 (2.5·10⁷) is comfortable. |
| Large | ≤ 10⁶ | O(n log n) | sorting, heaps, binary search per element | 10⁶ × 20 = 2·10⁷. |
| Huge | ≤ 10⁸ | O(n) | single pass, math | 10⁸ steps — only constant work per element fits. |
| Astronomical | > 10⁸ | O(log n) or O(1) | binary search on the answer, formulas | You can't even read every value. |
06 · java
Raw vs Collections Framework
Loop shapes → Big-O
class LoopShapes { // O(1): the same work whatever n is static int first(int[] a) { return a[0]; } // O(log n): n halves every step, so it reaches 1 after about log2(n) steps static int halvings(int n) { int steps = 0; while (n > 1) { n /= 2; steps++; } return steps; } // O(n): one pass static long sum(int[] a) { long total = 0; for (int x : a) total += x; return total; } // O(n log n): n times a halving loop static long nLogNSteps(int n) { long steps = 0; for (int i = 0; i < n; i++) for (int j = n; j > 1; j /= 2) steps++; return steps; } // O(n^2): every pair i < j -> n(n-1)/2 steps static long pairSteps(int n) { long steps = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) steps++; return steps; } // O(n + m), NOT O(n^2): two separate loops over two different inputs static long twoInputs(int[] a, int[] b) { long steps = 0; for (int x : a) steps++; for (int y : b) steps++; return steps; }}- Each method returns its own step count, so you can see the formula: halvings(10⁶) = 19, pairSteps(10) = 45 = 10·9/2.
- Two loops one after the other over different inputs is O(n + m), not O(n²) — only nesting multiplies.
j /= 2orj *= 2in a loop condition is the fingerprint of O(log n).
Exponential: when the call tree branches
class Exponential { // O(2^n): every element is either in or out of a subset -> 2^n leaves static long countSubsets(int i, int n) { if (i == n) return 1; // one complete subset return countSubsets(i + 1, n) // skip element i + countSubsets(i + 1, n); // take element i } // O(2^n)-ish: naive Fibonacci recomputes the same values again and again static long calls = 0; static long fib(int n) { calls++; return n < 2 ? n : fib(n - 1) + fib(n - 2); }}- A recursive function that calls itself twice on a problem only 1 smaller makes about 2ⁿ calls.
- Naive
fib(20)makes 21,891 calls for only 21 distinct arguments (0..20) — the repeated work that dynamic programming removes.
Hidden costs: library calls that loop for you
class Slow { // looks like O(n), is O(n^2): list.contains scans the whole list static int countDistinct(int[] nums) { List<Integer> seen = new ArrayList<>(); for (int x : nums) if (!seen.contains(x)) seen.add(x); // O(n) inside a loop return seen.size(); } // O(n^2): each += copies the whole string built so far static String join(int n) { String s = ""; for (int i = 0; i < n; i++) s += i % 10; return s; } // O(n^2): remove(0) shifts every remaining element left static long drainFront(List<Integer> list) { long sum = 0; while (!list.isEmpty()) sum += list.remove(0); return sum; }} class Fast { static int countDistinct(int[] nums) { Set<Integer> seen = new HashSet<>(); // O(1) average contains/add for (int x : nums) seen.add(x); return seen.size(); } static String join(int n) { StringBuilder sb = new StringBuilder(); // amortized O(1) append for (int i = 0; i < n; i++) sb.append(i % 10); return sb.toString(); } static long drainFront(Deque<Integer> deque) { long sum = 0; while (!deque.isEmpty()) sum += deque.pollFirst(); // O(1) at the front return sum; }}ArrayList.containsscans the list (O(n));HashSet.containshashes (O(1) average). Inside a loop that's O(n²) vs O(n).s += xbuilds a brand-new String each time (O(length)), so a loop of n concatenations is O(n²).StringBuilder.appendis amortized O(1).ArrayList.remove(0)shifts every element;ArrayDeque.pollFirst()is O(1). Use the right container for the access pattern.
Amortized growth: by hand vs ArrayList
class IntList { private int[] data = new int[1]; private int size = 0; long copies = 0; // total elements copied while growing (for the analysis) void add(int value) { if (size == data.length) { // full? int[] bigger = new int[data.length * 2]; // double the capacity for (int i = 0; i < size; i++) bigger[i] = data[i]; // O(size) copy, but rare copies += size; data = bigger; } data[size++] = value; // the usual O(1) case } int get(int i) { if (i < 0 || i >= size) throw new IndexOutOfBoundsException(i); return data[i]; } int size() { return size; } int capacity() { return data.length; }}class Library { static List<Integer> build(int n) { List<Integer> list = new ArrayList<>(); // grows by ~1.5x internally for (int i = 0; i < n; i++) list.add(i); // amortized O(1) per add return list; } static List<Integer> buildPresized(int n) { List<Integer> list = new ArrayList<>(n); // capacity known: no regrowth at all for (int i = 0; i < n; i++) list.add(i); return list; }}- Doubling means the copies are 1 + 2 + 4 + … (one power of two per growth, each < n) < 2n, so n adds do fewer than 3n units of work: amortized O(1).
- Java's
ArrayListgrows by about 1.5×: OpenJDK 17'sgrowaddsoldCapacity >> 1(half the old size). Any constant factor > 1 keeps adds amortized O(1). - Growing by a fixed amount (+10 each time) would make n adds O(n²) — the growth must be multiplicative.
- If you know the final size,
new ArrayList<>(n)avoids regrowth completely.
Space: the recursion stack counts
class RecursiveSum { /** Sum of a[i..]. Each call waits for the next one: n frames on the stack at once -> O(n) space. */ static long sum(int[] a, int i) { if (i == a.length) return 0; // base case long rest = sum(a, i + 1); // this frame pauses here return a[i] + rest; }}- Each call keeps its local variables alive until the call below it returns. n waiting calls = O(n) space.
- The JDK 17 docs list a 1024 KB default thread stack on Linux/x64 and macOS (
-Xsschanges it): recursion around 10⁴–10⁵ levels deep can throwStackOverflowError.
Shrinking the stack: loop, or halve
class IterativeSum { /** Same answer with a loop: one frame, O(1) extra space. */ static long sum(int[] a) { long total = 0; for (int x : a) total += x; return total; }} class HalvingSum { /** Splits the range in half: still O(n) time, but the stack is only O(log n) deep. */ static long sum(int[] a, int lo, int hi) { // sums a[lo..hi) if (hi - lo == 0) return 0; if (hi - lo == 1) return a[lo]; int mid = (lo + hi) >>> 1; return sum(a, lo, mid) + sum(a, mid, hi); } static int maxDepth(int lo, int hi) { if (hi - lo <= 1) return 1; int mid = (lo + hi) >>> 1; return 1 + Math.max(maxDepth(lo, mid), maxDepth(mid, hi)); }}- Same O(n) time for all three versions — only the space changes: O(n) → O(1) (loop) or O(log n) (halving).
- Divide-and-conquer recursion (merge sort, binary search, tree recursion on balanced trees) is O(log n) deep.
| call | does | cost |
|---|---|---|
list.get(i) / list.set(i, x) | ArrayList random access | O(1) |
list.add(x) | Append to ArrayList | O(1) amortized |
list.add(0, x) / list.remove(0) | Insert/remove at the front of an ArrayList (shifts everything) | O(n) |
list.contains(x) | Linear search | O(n) |
set.contains(x) / map.get(k) | HashSet / HashMap lookup | O(1) average, O(log n) worst for large Comparable-key bins |
treeMap.get(k) / treeSet.add(x) | Sorted map/set (red-black tree) | O(log n) |
Arrays.sort(a) | Sort an array | O(n log n) |
s.substring(i, j) | Copies j − i characters into a new String | O(j − i) |
sb.append(x) | StringBuilder append | O(1) amortized per char |
deque.offerLast / pollFirst | ArrayDeque at either end | O(1) amortized |
Membership tests inside a loop
→ HashSet, not List.contains
O(1) average vs O(n) per test.
Building a long string piece by piece
→ StringBuilder
Amortized O(1) appends instead of O(n) copies.
Removing from the front repeatedly
→ ArrayDeque
O(1) at both ends; ArrayList shifts on every remove(0).
Deep recursion (n ≥ ~10⁴)
→ An explicit loop or stack
Avoids StackOverflowError; same time, less risk.
Known final size
→ new ArrayList<>(n) / new int[n]
No regrowth copies at all.
07 · recognise
Spot the pattern
A loop variable that halves or doubles (i /= 2, i *= 2, lo..hi shrinking by half)
O(log n)
A loop nested inside another loop over the same input
O(n²) — unless the inner pointer never resets (then it's O(n) total)
Two pointers or a sliding window where each pointer only moves forward
O(n) amortized: each index is visited a constant number of times
Sorting before the main loop
At least O(n log n)
Recursion with two calls on n − 1
O(2ⁿ) — look for repeated subproblems (DP) to fix it
Recursion that halves the input and does O(n) work per level
O(n log n) (merge sort shape)
Constraints with n ≤ 20 or n ≤ 10
Exponential or factorial search is intended
08 · traps & tricks
Mistakes to avoid, tricks to use
traps
- Calling a nested loop O(n²) when the inner loop's pointer never resets — two pointers / sliding window are O(n).
- Forgetting library costs:
contains,indexOf,remove(0),substring,+=on strings are O(n). - Ignoring the recursion stack when stating space complexity.
- Saying HashMap is "always O(1)" — it's O(1) average. Say "average" in interviews.
- Writing O(2n) or O(n + 5) — drop constants: O(n).
- Treating two different inputs as one: a loop over n strings each of length m is O(n·m), not O(n²).
- Counting output size as free: generating all subsets is at least O(2ⁿ · n) because each subset must be written.
tricks
- State complexity with a reason in one breath: "O(n log n) — the sort dominates; the scan after it is O(n)."
- Name your variables in Big-O: n = array length, m = string length, V/E for graphs. It prevents mixing them up.
- For recursion, draw the call tree: time ≈ number of nodes × work per node; space ≈ height of the tree.
- If the constraints say n ≤ 10⁵, immediately rule out O(n²) before you start designing.
- Quote time and space every time — interviewers almost always ask for both.
09 · why & how
Questions you might be too shy to ask
Why do we drop constants? Isn't 2n slower than n?
It is, by a factor of 2 — but that factor depends on the machine, the language and the compiler. Big-O captures what doesn't change: how the work scales. An O(n) algorithm will always beat an O(n²) one once n is big enough, whatever the constants.
Does O(n) tell me how many seconds my code takes?
No. It tells you how the step count grows: double n, and O(n) work doubles while O(n²) work becomes 4×. To guess seconds, plug in the max n and use the rough budget of ~10⁸ simple steps per second. n = 10⁶ with O(n) ≈ 10⁶ steps — far under a second.
What is the base of the log in O(log n)?
It doesn't matter in Big-O: log₂ n and log₁₀ n differ only by a constant factor (log₂ n ≈ 3.32 · log₁₀ n). In practice we think in base 2 because we usually halve.
Is O(n log n) closer to O(n) or to O(n²)?
Much closer to O(n). At n = 10⁶, log₂ n is only about 20, so n log n ≈ 2·10⁷ steps. n² is 10¹² — fifty thousand times more. That's why "sort first, then one pass" is almost always fine.
My inner loop starts at j = i + 1, so it checks only half the pairs. Why is it still O(n²)?
Half the pairs is n(n − 1)/2. For n = 10⁴ that's about 5·10⁷ — still huge. Big-O drops the ½ (a constant), so it stays O(n²). Halving the work never changes the shape; removing the inner loop does.
Is i < nums.length or i < s.length() in a loop condition slow?
No. nums.length, s.length() and list.size() are O(1): Java stores the size, it doesn't count every time. Saving int n = nums.length; first is only for readability. The calls to watch inside loops are contains, indexOf, substring, remove(0) and += on strings.
Which case should I quote — best, average or worst?
Worst case by default, because it's a guarantee. When the average is the honest story (HashMap, quicksort, Rabin–Karp), say so explicitly: "quicksort is O(n log n) average, O(n²) worst", or "HashMap is O(1) average; since Java 8 the worst case is O(log n) for Comparable keys."
What does amortized actually mean?
Spread the cost of rare expensive operations over all operations. ArrayList's add sometimes copies n elements, but those copies happen so rarely that n adds cost O(n) in total — so each add is O(1) amortized. It's a guarantee over a sequence, not a probability.
Is O(n) always faster than O(n²)?
For large n, yes. For tiny n, constants can win — that's why OpenJDK's Arrays.sort switches to insertion sort (O(n²)) for very small pieces (an implementation detail, not part of the spec). In interviews, Big-O is what matters.
Does the output count toward space complexity?
Usually not — we report extra (auxiliary) space. The input array you were given doesn't count either, so changing it in place is O(1) extra. Say it explicitly: "O(1) extra space, not counting the output list."
How do I find the Big-O of my own code quickly?
Find the innermost repeated operation, multiply the sizes of the loops around it, add separate phases together, keep the biggest term. For recursion: number of calls × work per call.
LeetCode says "Time Limit Exceeded" but my answer is correct. What does that mean?
Your logic is right, but it's too slow for the biggest hidden test. Check the constraints: n = 10⁵ with an O(n²) loop is 10¹⁰ steps. Small tweaks (faster I/O, fewer ifs) rarely save you. Find the repeated work and change the complexity class instead.
Sqrt(x): why while (lo <= hi) and not lo < hi?
With <=, the last candidate (when lo == hi) still gets checked. Try x = 1 with <: lo = 0, hi = 1, mid = 0 fits, lo becomes 1, and the loop stops before ever testing 1. It returns 0 — wrong. With <=, mid = 1 is tested and the answer is 1.
Sqrt(x): √x is much smaller than x, so why start with hi = x?
Because x is a range that surely contains the answer, and it's simple. A loose range costs almost nothing: halving 2³¹ down to 1 takes only about 31 steps. Dhyan do: lo, hi and mid are long, so mid * mid can't overflow even for mid near 2³¹.
10 · practice
Interview problems
Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.
- #69Sqrt(x)EasyByteDance / TikTokBloombergAmazonGoogleApple+1
Also practise this here
Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.
- #217Contains DuplicateEasyin Hashing
One question, three costs: O(n²) pairs, O(n log n) sort, O(n) average with a HashSet — the cleanest Big-O comparison.
- #268Missing NumberEasyin Bits
The same answer in O(n log n), in O(n) time with O(n) space, and in O(n) time with O(1) space: space complexity matters too.
11 · revise
The whole chapter on one screen
8 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.
- what it is
Big-O counts how the number of steps grows with the input size n. Constants and small terms drop: 3n + 5 → O(n); n² + 100n → O(n²).
- use it when
Before coding, turn the constraints into a budget. While explaining, give time and space, each with a one-line reason.
- cost
At n = 10⁶: log n ≈ 20 · n log n ≈ 2·10⁷ · n² = 10¹². A judge allows roughly 10⁸ simple steps per second.
- template
Loops in sequence add (O(n + m)). Nested loops multiply (O(n·m)). A loop that halves is O(log n). Recursion = calls × work per call.
- trap
Hidden loops:
list.contains,list.remove(0),substring,s += xare O(n). Inside a loop they quietly make O(n²). - trap
"HashMap is O(1)" — say average. And the recursion stack is space: n waiting calls = O(n), even with no arrays.
- pro tip
Amortized O(1):
ArrayList.addsometimes copies everything, but capacity grows ~1.5×, so n adds cost O(n) in total. - pro tip
An inner pointer that never moves back (two pointers, sliding window) is O(n) overall, not O(n²). Count pointer moves.
12 · recall
Flip, remember, repeat
Why is 3n + 5 written as O(n)?
Question 1: Why is 3n + 5 written as O(n)?
13 · check yourself
Quick quiz
What is the time complexity of `for (int i = 1; i < n; i *= 2) { ... O(1) ... }`?
Two separate (not nested) loops: one over n items, one over m items. Complexity?
Constraints say n ≤ 2·10⁵. Which is the slowest complexity that's safe?
Why is ArrayList.add O(1) amortized even though it sometimes copies the whole array?
A recursive function calls itself once with n − 1 and does O(1) work otherwise. Space complexity?
What is the complexity of this loop: `for (String w : words) result += w;` with n words of length k?
HashMap.get is best described as…
14 · learn more
A second teacher, if you want one
- ▶ videoTime and Space Complexity COMPLETE Tutorial - What is Big O? ↗Kunal Kushwaha · EnglishA long, careful tour of Big-O, Omega and Theta, recurrences, and the cost of recursive code. Watch it in parts; every later chapter uses it.
- ▶ videoTime and Space Complexity - Strivers A2Z DSA Course ↗Striver (take U forward) · EnglishShort and practical: counting steps, why constants drop, worst vs average case, and the time limits judges actually use.
- ▶ videoSignificance Of The Constraints | How To Solve Any Coding Problem In Your Interview Part 2 ↗Aditya Verma · HindiRead the limit on n first, and it tells you which complexity will pass, before you write a single line of a TLE solution.