Analyze Code Complexity
Why Practice Complexity Analysis?
Understanding Big-O notation in theory is one thing. Looking at real code and calculating its complexity from scratch is another skill entirely — and it is the one interviewers actually test.
In a technical interview, you will not be asked "what is O notation?" You will be asked "what is the time complexity of this solution?" while pointing at code you just wrote. The ability to analyze code on the spot, explain your reasoning aloud, and identify where the bottleneck is — that is the skill this topic builds.
This page works through complexity analysis systematically. You will learn a consistent set of rules, apply them to progressively complex code patterns, and build the instinct to read any algorithm and immediately know its complexity.
The Four Rules of Complexity Analysis
Before analyzing any code, internalize these four rules. They cover almost every situation you will encounter.
Rule 1 — Single statements are O(1).
Any single operation — variable assignment, arithmetic, array access, comparison — runs in constant time. It does not matter how complex the expression looks. If it is one statement with no loops or recursion, it is O(1).
Rule 2 — Sequential blocks add their complexities.
If block A runs in O(f(n)) and block B runs in O(g(n)) and they run one after the other, the total is O(f(n) + g(n)). Then simplify by keeping only the dominant term.
Rule 3 — Nested blocks multiply their complexities.
If an O(f(n)) block runs inside an O(g(n)) loop, the total is O(f(n) × g(n)). A loop running n times that contains another loop running n times gives O(n × n) = O(n²).
Rule 4 — Drop constants and lower-order terms.
O(3n² + 5n + 12) simplifies to O(n²). The constant 3, the linear term 5n, and the fixed term 12 all become irrelevant as n grows large. Keep only the fastest-growing term.
With these four rules, you can analyze almost any iterative algorithm mechanically.
Pattern 1: Single Loop — O(n)
The most fundamental pattern. A single loop that iterates through all n elements performs n iterations of whatever is inside. If the body is O(1), the total is O(n).
1public class SingleLoop {
2
3 public static void analyzeLoop(int[] arr) {
4 int sum = 0; // O(1) — single assignment
5
6 // This loop runs exactly n times
7 for (int i = 0; i < arr.length; i++) { // O(n) — n iterations
8 sum += arr[i]; // O(1) — single operation per iteration
9 }
10
11 System.out.println("Sum: " + sum); // O(1) — single statement
12
13 // Total: O(1) + O(n) * O(1) + O(1)
14 // = O(1) + O(n) + O(1)
15 // = O(n) ← dominant term wins
16 }
17
18 public static void main(String[] args) {
19 int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6};
20 analyzeLoop(numbers);
21 }
22}Output:
Sum: 31
Complexity Breakdown
Line by line: int sum = 0 → O(1) for loop header → runs n times sum += arr[i] → O(1) per iteration → n × O(1) = O(n) println → O(1) Sequential total: O(1) + O(n) + O(1) Simplification: O(n) ← O(1) terms are dominated by O(n) Time Complexity: O(n) Space Complexity: O(1) ← only the variable 'sum' is created
Pattern 2: Two Sequential Loops — O(n)
A common beginner mistake is thinking two loops means O(2n) which is "different" from O(n). It is not. Constants are dropped. Two sequential loops of size n give O(n) + O(n) = O(2n) = O(n).
1public class TwoSequentialLoops {
2
3 public static void analyzeTwo(int[] arr) {
4 // First loop — runs n times
5 int max = arr[0];
6 for (int i = 1; i < arr.length; i++) { // O(n)
7 if (arr[i] > max) max = arr[i];
8 }
9
10 // Second loop — runs n times (sequential, not nested)
11 int min = arr[0];
12 for (int i = 1; i < arr.length; i++) { // O(n)
13 if (arr[i] < min) min = arr[i];
14 }
15
16 System.out.println("Max: " + max + ", Min: " + min);
17
18 // Total: O(n) + O(n) = O(2n) = O(n)
19 // Two sequential loops do NOT give O(n²)
20 }
21
22 public static void main(String[] args) {
23 int[] numbers = {3, 1, 4, 1, 5, 9, 2, 6};
24 analyzeTwo(numbers);
25 }
26}Output:
Max: 9, Min: 1
Complexity Breakdown
First loop: O(n) — finds maximum Second loop: O(n) — finds minimum Sequential total: O(n) + O(n) = O(2n) Drop constant: O(n) Time Complexity: O(n) Space Complexity: O(1) — only max and min variables created Key rule: sequential loops ADD, not multiply. Two separate O(n) loops = O(n), not O(n²).
Pattern 3: Nested Loops — O(n²)
When a loop runs inside another loop, and both depend on n, complexities multiply. This is the most important pattern to recognize quickly — it is the hallmark of quadratic algorithms.
1public class NestedLoops {
2
3 // Check all pairs — classic O(n²) pattern
4 public static void findAllPairs(int[] arr) {
5 int pairCount = 0;
6
7 // Outer loop — runs n times
8 for (int i = 0; i < arr.length; i++) { // O(n)
9
10 // Inner loop — runs n times for EACH outer iteration
11 for (int j = i + 1; j < arr.length; j++) { // O(n)
12 // This body executes n*(n-1)/2 times total
13 System.out.println("Pair: (" + arr[i] + ", " + arr[j] + ")");
14 pairCount++;
15 }
16 }
17
18 System.out.println("Total pairs: " + pairCount);
19 // Total: O(n) * O(n) = O(n²)
20 }
21
22 public static void main(String[] args) {
23 int[] numbers = {1, 2, 3, 4};
24 findAllPairs(numbers);
25 }
26}Output:
Pair: (1, 2)
Pair: (1, 3)
Pair: (1, 4)
Pair: (2, 3)
Pair: (2, 4)
Pair: (3, 4)
Total pairs: 6
Complexity Breakdown
Outer loop: runs n times
Inner loop: runs (n-1), (n-2), ..., 1 times for each outer step
Total inner iterations = (n-1) + (n-2) + ... + 1
= n(n-1)/2
≈ n²/2
Drop constant (1/2): O(n²)
For n=4: 4*3/2 = 6 pairs ← matches output
For n=10: 10*9/2 = 45 pairs
For n=100: 100*99/2 = 4950 pairs
Time Complexity: O(n²)
Space Complexity: O(1) — only pairCount variable created
Key rule: nested loops MULTIPLY.
Outer O(n) × Inner O(n) = O(n²)
Pattern 4: Loop with Halving — O(log n)
When a loop variable is divided (or multiplied) by a constant each iteration rather than incremented by 1, the loop runs logarithmically. This is the signature of O(log n) algorithms.
1public class HalvingLoop {
2
3 // Count how many times n can be halved before reaching 1
4 public static void analyzeHalving(int n) {
5 int count = 0;
6 int value = n;
7
8 // Each iteration divides value by 2 — not increments by 1
9 while (value > 1) { // runs log₂(n) times
10 value = value / 2;
11 count++;
12 System.out.println("Step " + count + ": value = " + value);
13 }
14
15 System.out.println("Total steps for n=" + n + ": " + count);
16 // Total: O(log n) — value halves each iteration
17 }
18
19 public static void main(String[] args) {
20 analyzeHalving(64);
21 System.out.println();
22 analyzeHalving(1000);
23 }
24}Output:
Step 1: value = 32
Step 2: value = 16
Step 3: value = 8
Step 4: value = 4
Step 5: value = 2
Step 6: value = 1
Total steps for n=64: 6
Step 1: value = 500
Step 2: value = 250
Step 3: value = 125
Step 4: value = 62
Step 5: value = 31
Step 6: value = 15
Step 7: value = 7
Step 8: value = 3
Step 9: value = 1
Total steps for n=1000: 9
Complexity Breakdown
n=64: 6 steps → log₂(64) = 6 ✓
n=1000: 9 steps → log₂(1000) ≈ 9.97 ≈ 10 ✓
Pattern: when the loop variable is halved each step,
the loop runs log₂(n) times.
Why? Starting from n:
After 1 step: n/2
After 2 steps: n/4
After k steps: n/2^k
Loop ends when n/2^k = 1 → k = log₂(n)
Time Complexity: O(log n)
Space Complexity: O(1)
Recognition tip: if you see /= 2 or *= 2 controlling a loop,
think O(log n) immediately.
Pattern 5: Nested Loop with Different Variables — O(n × m)
Not all nested loops give O(n²). When the outer and inner loops iterate over different collections of different sizes (n and m), the complexity is O(n × m), not O(n²).
1public class TwoVariableLoop {
2
3 // Search for any common element between two arrays
4 // Outer loop: size n, Inner loop: size m → O(n × m)
5 public static boolean hasCommonElement(int[] arr1, int[] arr2) {
6 // Outer loop iterates over arr1 — size n
7 for (int i = 0; i < arr1.length; i++) { // O(n)
8
9 // Inner loop iterates over arr2 — size m
10 for (int j = 0; j < arr2.length; j++) { // O(m)
11 if (arr1[i] == arr2[j]) {
12 return true;
13 }
14 }
15 }
16
17 return false;
18 // Total: O(n × m) — NOT O(n²) unless arr1.length == arr2.length
19 }
20
21 public static void main(String[] args) {
22 int[] a = {1, 3, 5, 7};
23 int[] b = {2, 4, 6, 8, 10, 12};
24
25 System.out.println("Common element exists: " + hasCommonElement(a, b));
26
27 int[] c = {1, 3, 5, 7};
28 int[] d = {7, 9, 11};
29
30 System.out.println("Common element exists: " + hasCommonElement(c, d));
31 }
32}Output:
Common element exists: false
Common element exists: true
Complexity Breakdown
arr1 has n elements, arr2 has m elements. Outer loop: n iterations Inner loop: m iterations per outer step Total: n × m iterations If n = m: O(n × n) = O(n²) If n != m: O(n × m) — must keep both variables Time Complexity: O(n × m) Space Complexity: O(1) Recognition tip: count the distinct size variables. One size → O(n^k) where k is nesting depth. Two sizes → O(n × m).
Pattern 6: Recursive Algorithms — O(n) and O(log n)
Recursion requires a different analysis approach. You cannot just count loops. Instead, identify how many recursive calls are made and what work each call does.
The two most common recursive patterns:
- ›Linear recursion — one call per level, n levels deep → O(n)
- ›Halving recursion — one call per level, log n levels deep → O(log n)
1public class RecursionComplexity {
2
3 // Linear recursion — one call reduces n by 1 each time
4 // Depth: n levels → O(n) time, O(n) stack space
5 public static int sumRecursive(int n) {
6 if (n <= 0) return 0; // Base case — O(1)
7 return n + sumRecursive(n - 1); // One recursive call, n reduced by 1
8 }
9
10 // Halving recursion — one call reduces n by half each time
11 // Depth: log₂(n) levels → O(log n) time, O(log n) stack space
12 public static int countHalves(int n) {
13 if (n <= 1) return 0; // Base case — O(1)
14 return 1 + countHalves(n / 2); // One recursive call, n halved
15 }
16
17 public static void main(String[] args) {
18 System.out.println("Sum 1 to 6: " + sumRecursive(6));
19 System.out.println("Halving steps for 64: " + countHalves(64));
20 }
21}Output:
Sum 1 to 6: 21
Halving steps for 64: 6
Dry Run: Recursive Call Trees
sumRecursive(6) — Linear Recursion:
sumRecursive(6)
→ sumRecursive(5)
→ sumRecursive(4)
→ sumRecursive(3)
→ sumRecursive(2)
→ sumRecursive(1)
→ sumRecursive(0) → return 0
return 1 + 0 = 1
return 2 + 1 = 3
return 3 + 3 = 6
return 4 + 6 = 10
return 5 + 10 = 15
return 6 + 15 = 21
Call depth: 7 (n+1 levels) → O(n) time, O(n) space
countHalves(64) — Halving Recursion:
countHalves(64) → countHalves(32) → countHalves(16)
→ countHalves(8) → countHalves(4) → countHalves(2)
→ countHalves(1) → return 0
Call depth: 7 (log₂(64) = 6, plus base) → O(log n) time, O(log n) space
Key insight: count the call depth, not just the number of calls.
Pattern 7: Mixed Complexity — O(n log n)
Some algorithms combine a loop with a halving operation inside, or recurse log n levels and do O(n) work at each level. Both patterns give O(n log n).
1public class NLogN {
2
3 // For each element, perform a binary search — O(n log n) total
4 public static void searchEachElement(int[] arr, int[] sortedArr) {
5 // Outer loop — runs n times
6 for (int i = 0; i < arr.length; i++) { // O(n)
7
8 // Binary search inside — O(log n) per call
9 int left = 0, right = sortedArr.length - 1;
10 boolean found = false;
11
12 while (left <= right) { // O(log n)
13 int mid = left + (right - left) / 2;
14 if (sortedArr[mid] == arr[i]) {
15 found = true;
16 break;
17 } else if (sortedArr[mid] < arr[i]) {
18 left = mid + 1;
19 } else {
20 right = mid - 1;
21 }
22 }
23
24 System.out.println(arr[i] + ": " + (found ? "found" : "not found"));
25 }
26 // Total: O(n) * O(log n) = O(n log n)
27 }
28
29 public static void main(String[] args) {
30 int[] items = {3, 7, 1, 9};
31 int[] sorted = {1, 2, 3, 4, 5, 6, 7, 8};
32 searchEachElement(items, sorted);
33 }
34}Output:
3: found
7: found
1: found
9: not found
Complexity Breakdown
Outer loop: runs n times → O(n) Binary search inside: runs log m times → O(log m) If m ≈ n (both arrays similar size): Total: O(n) × O(log n) = O(n log n) This is the same growth rate as Merge Sort and Heap Sort. Time Complexity: O(n log n) Space Complexity: O(1) — only pointer variables (left, right, mid) Recognition tip: loop containing binary search, or merge-sort-style recursion → O(n log n)
Full Complexity Reference Table
Here is a summary of every pattern covered, with recognition cues for interviews:
| Pattern | Complexity | Recognition Cue |
|---|---|---|
| Single statement | O(1) | No loops, no recursion |
| Single loop over n | O(n) | for i in 0..n |
| Two sequential loops | O(n) | Two separate loops, same n |
| Loop with constant inner work | O(n) | Outer n, inner fixed iterations |
| Nested loops over n | O(n²) | Loop inside loop, both over n |
| Nested loops over n and m | O(n × m) | Two different array sizes |
| Loop that halves | O(log n) | /= 2 or *= 2 in loop |
| Loop with binary search inside | O(n log n) | Outer n, inner binary search |
| Linear recursion depth n | O(n) | f(n-1) pattern |
| Halving recursion depth log n | O(log n) | f(n/2) pattern |
| Two recursive calls per level | O(2^n) | f(n-1) + f(n-1) pattern |
The Step-by-Step Analysis Method
When asked about complexity in an interview, walk through this method aloud. It shows clear thinking and covers every case.
Step 1: Identify all loops and their relationship to n.
→ Is it a single loop? Sequential loops? Nested?
→ Does it run n times, log n times, or a constant?
Step 2: Identify any recursion.
→ How many calls per level?
→ How does n change per call? (n-1 → linear, n/2 → log n)
→ What work is done at each level?
Step 3: Apply the rules.
→ Sequential blocks: add complexities
→ Nested blocks: multiply complexities
→ Recursion: multiply (calls per level) by (work per level)
Step 4: Drop constants and lower-order terms.
→ O(3n² + 5n + 2) → O(n²)
→ O(n + log n) → O(n)
→ O(2n) → O(n)
Step 5: State time and space complexity separately.
→ Space: count auxiliary data structures and recursion depth
Common Mistakes Beginners Make
Thinking two loops always means O(n²). Sequential loops add, not multiply. Two separate O(n) loops give O(n), not O(n²). Only nested loops multiply.
Forgetting the inner loop might not always run n times. In the all-pairs example, the inner loop runs n-1, n-2, ..., 1 times. The total is n(n-1)/2 — still O(n²) after dropping constants, but not literally n² iterations.
Ignoring recursion stack space. When analyzing space complexity of recursive functions, always count the call stack depth. A function that looks O(1) in variables may be O(n) or O(log n) in total space due to recursion.
Assuming a constant-size inner operation always makes the outer loop O(n). This is usually true. But if the "constant" inner operation is actually calling a function that takes O(n) time internally, the outer loop becomes O(n²). Always check what functions inside loops actually do.
Not looking at what controls the loop termination. The termination condition determines the complexity. i < n with i++ is O(n). i < n with i *= 2 is O(log n). The increment, not just the condition, defines the growth.
Interview Questions
Q: How do you analyze the time complexity of a function with nested loops?
Identify the number of times each loop runs in terms of n. Multiply the complexities of nested loops — an outer loop running n times containing an inner loop running n times gives O(n²). Then drop constants and lower-order terms. Always check whether the inner loop's iteration count depends on the outer variable, which affects the exact coefficient but rarely the Big-O class.
Q: What is the time complexity of a loop that divides its variable by 2 each iteration?
O(log n). Starting from n, after k iterations the variable is n/2^k. The loop ends when n/2^k reaches 1, which means k = log₂(n). Any loop controlled by repeated halving (or doubling) runs in O(log n).
Q: How do you calculate the space complexity of a recursive algorithm?
Identify the maximum recursion depth — how many stack frames exist simultaneously at peak depth. Linear recursion (f(n-1)) reaches depth n, using O(n) stack space. Halving recursion (f(n/2)) reaches depth log n, using O(log n) stack space. Add any auxiliary data structures allocated across all calls.
Q: Two functions run sequentially — first takes O(n log n), second takes O(n). What is the total complexity?
O(n log n). Sequential operations add: O(n log n) + O(n) = O(n log n + n). Since n log n grows faster than n for large n, the lower-order term is dropped: O(n log n).
FAQs
How do I know when to stop simplifying?
Stop when only the single fastest-growing term remains, with no constants. O(5n² + 3n + 100) → O(n²). O(n log n + n²) → O(n²). O(2 log n) → O(log n). Keep asking: "does this term grow faster than all others as n approaches infinity?"
Does the complexity change if the array is already sorted?
For some algorithms, yes. Insertion Sort is O(n) on already-sorted input (best case) but O(n²) in the worst case. Binary Search requires a sorted array and is O(log n) regardless. When analyzing, always consider whether input properties (sorted, reversed, duplicates) affect which case applies.
What if I cannot tell how many times a recursive function calls itself?
Draw the recursion tree. Each node is one function call. Count the number of nodes (total calls) and the work done at each node. Multiply them. For Fibonacci (two calls per level, n levels), the tree has 2^n nodes — that is O(2^n). For merge sort (two calls per level, log n levels, O(n) work per level), the tree gives O(n log n).
Is it possible to have better than O(n) for a problem that requires reading all elements?
No. If a problem requires examining every element (like finding the sum or maximum), O(n) is the theoretical lower bound. No algorithm can do better without missing elements. O(n) for such problems is optimal, not slow.
Quick Quiz
Question 1: What is the time complexity of this code?
for i from 0 to n:
for j from 0 to 10: ← always 10 iterations, not n
print(i + j)
- ›A) O(n²)
- ›B) O(10n)
- ›C) O(n)
- ›D) O(10)
Answer: C) O(n). The inner loop always runs exactly 10 times — a constant. Constant factors are dropped: O(n × 10) = O(10n) = O(n). Only the outer loop depends on n.
Question 2: What is the time complexity of this code?
i = n
while i > 0:
j = 0
while j < i:
j++
i = i // 2
- ›A) O(n)
- ›B) O(n²)
- ›C) O(n log n)
- ›D) O(log n)
Answer: C) O(n log n). The outer loop halves i each time — runs log n times. The inner loop runs i times per outer iteration: n + n/2 + n/4 + ... ≈ 2n total inner iterations across all outer steps. O(n) inner work × O(log n) outer steps = O(n log n).
Question 3: A recursive function calls itself twice per call and reduces n by 1 each time. What is its time complexity?
- ›A) O(n)
- ›B) O(n log n)
- ›C) O(2^n)
- ›D) O(log n)
Answer: C) O(2^n). Two calls per level, n levels deep. The recursion tree has 2^0 + 2^1 + ... + 2^n = 2^(n+1) - 1 nodes ≈ O(2^n). This is the naive Fibonacci pattern — exponential growth.
Question 4: What is the total complexity when an O(n²) block runs first, then an O(n log n) block runs after?
- ›A) O(n² × n log n)
- ›B) O(n² + n log n) = O(n²)
- ›C) O(n log n)
- ›D) O(n³)
Answer: B) O(n² + n log n) = O(n². Sequential blocks add. O(n²) + O(n log n) = O(n² + n log n). Since n² grows faster than n log n, the lower-order term is dropped, giving O(n²).
Summary
Analyzing code complexity is a learnable, mechanical skill built on four rules: single statements are O(1), sequential blocks add, nested blocks multiply, and lower-order terms get dropped.
The key patterns to recognize instantly:
- ›Single loop over n → O(n)
- ›Two sequential loops over n → O(n) not O(n²)
- ›Loop inside loop both over n → O(n²)
- ›Loop that halves its variable → O(log n)
- ›Loop containing binary search → O(n log n)
- ›Recursion reducing by 1 per call → O(n) time, O(n) space
- ›Recursion halving per call → O(log n) time, O(log n) space
- ›Two recursive calls per level, n levels → O(2^n)
Practice applying these rules to every piece of code you write. After analyzing fifty algorithms, the complexity becomes immediately obvious — you will not need to count. You will just see it.
In the next topic, you will learn How to Approach Problems — combining everything from complexity analysis, algorithm thinking, and data structure selection into a systematic method for solving new problems from scratch.