DSA Complexity
Time complexity
The query hits at n = 10^7. Two algorithms both "work" on the sample. Only one stays inside the one-second budget when traffic is real.
Time complexity models how work grows with input size. Use , , and a clear before arguing that one algorithm scales.
Algorithm journey
Name n
What is the input size parameter?
Name the cost
Comparisons, writes, probes, or wall-ish abstract steps?
Name the case
Worst, average/expected, best, or amortized?
Drop lower terms
Classify growth, then benchmark constants that matter.
What actually happens
Naive idea: time an algorithm once on your laptop and call it fast. Brittle across machines and n.
Better idea: asymptotic vocabulary to reject bad scaling, then measure constants on realistic n.
It still fails if you hide the case ("O(n) on average" said as "O(n)") or count the wrong operation.
Invariant
A complexity claim stays meaningful only while the cost model, input parameter, and case (worst/expected/amortized) remain the ones you stated.
How to choose a complexity story
1. Can you state n and the counted operation in one sentence? If not, the Big-O claim is underspecified.
2. Do you need a worst-case SLA or an expected-case argument? Say which. Randomized algorithms live on expectations.
3. Are constants decisive at your n? Asymptotics filter; benchmarks decide crossovers.
Quantitative check
At n = 10^3, n^2 = 10^6 is often fine. At n = 10^7, n^2 = 10^14 is not. log2(10^7) ≈ 23 shows why logarithmic search changes product behavior.
What is Big O notation?
Big-O is an asymptotic upper bound, not a synonym for worst case. We can give an O(n²) upper bound for a best-case function too; the case and the notation are separate dimensions. In practice, use the tightest useful bound and explicitly name the input distribution or adversary.
Format: O(f(n)) where n = input size, f(n) = growth function
We drop constants and lower-order terms: O(2n + 100) → O(n), O(n² + n) → O(n²)
Note: Why Drop Constants?
Constants disappear from the classification, not from production latency. O(100n) and O(n) are the same asymptotic class, yet the former can lose throughout the input sizes a service actually sees. Use asymptotics to reject poor scaling, then benchmark realistic workloads to find the crossover point.
Common complexity classes
O(1) - Constant Time ⚡
Runtime doesn't change with input size.
Example: Accessing array[5], checking if number is even
O(log n) - Logarithmic Time 📈
Cuts problem in half each step.
Example: Binary search, balanced tree operations
O(n) - Linear Time 📏
Runtime grows proportionally with input.
Example: Linear search, finding max in array
O(n log n) - Linearithmic Time 🔄
Efficient sorting algorithms.
Example: Merge sort, quick sort (average), heap sort
O(n²) - Quadratic Time ⚠️
Nested loops over input.
Example: Bubble sort, selection sort, insertion sort
O(2ⁿ) - Exponential Time 💥
Doubles with each additional input.
Example: Recursive Fibonacci, subset generation
Interactive growth visualization
Complexity growth lab
Compare orders of growth on a logarithmic bar scale. Operation counts are a model, not a wall-clock benchmark.
The logarithmic scale keeps small classes visible. Real latency also depends on constants, allocation, cache misses, branch prediction, I/O, and parallelism; asymptotics become decisive only after the crossover point.
🎯 Key Insight: Growth Rates Matter!
For small inputs (n = 10), all algorithms seem fast. But as n grows:
- • n = 1,000: O(n) = 1K ops, O(n²) = 1M ops (1000x slower!)
- • n = 1,000,000: n = 1M modeled ops, while n² = 1 trillion modeled ops.
- • n = 100: 2ⁿ ≈ 1.27 × 10³⁰ modeled states, far beyond exhaustive enumeration.
This is why choosing the right algorithm matters for large datasets!
💻 Analyzing Code Examples
Example 1: O(1): constant number of modeled operations
Python
def first_or_none(values: list[int]) -> int | None:
"""Return the first value without scanning the collection."""
return values[0] if values else None
if __name__ == "__main__":
print(first_or_none([7, 11, 42]))Java
public class ConstantTimeExample {
static Integer firstOrNull(int[] values) {
return values.length == 0 ? null : values[0];
}
public static void main(String[] args) {
System.out.println(firstOrNull(new int[] {7, 11, 42}));
}
}Example 2: Θ(n): a full scan is necessary
Python
def maximum(values: list[int]) -> int:
if not values:
raise ValueError("maximum requires at least one value")
best = values[0]
for value in values[1:]:
if value > best:
best = value
return best
if __name__ == "__main__":
print(maximum([8, 3, 14, 2]))Java
public class LinearTimeExample {
static int maximum(int[] values) {
if (values.length == 0) {
throw new IllegalArgumentException("maximum requires a value");
}
int best = values[0];
for (int i = 1; i < values.length; i++) {
if (values[i] > best) best = values[i];
}
return best;
}
public static void main(String[] args) {
System.out.println(maximum(new int[] {8, 3, 14, 2}));
}
}Example 3: Θ(n²): all ordered pairs
Python
def pair_count(values: list[int]) -> int:
"""Count pairs without printing, so I/O does not hide the loop cost."""
count = 0
for _left in values:
for _right in values:
count += 1
return count
if __name__ == "__main__":
print(pair_count([1, 2, 3, 4])) # 16Java
public class QuadraticTimeExample {
static long pairCount(int[] values) {
long count = 0L;
for (int ignoredLeft : values) {
for (int ignoredRight : values) {
count++;
}
}
return count;
}
public static void main(String[] args) {
System.out.println(pairCount(new int[] {1, 2, 3, 4}));
}
}Example 4: Θ(log n): halve a sorted search interval
Python
def binary_search(values: list[int], target: int) -> int:
low, high = 0, len(values) - 1
while low <= high:
middle = low + (high - low) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
if __name__ == "__main__":
print(binary_search([2, 5, 8, 13, 21], 13))Java
public class LogarithmicTimeExample {
static int binarySearch(int[] values, int target) {
int low = 0;
int high = values.length - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) return middle;
if (values[middle] < target) low = middle + 1;
else high = middle - 1;
}
return -1;
}
public static void main(String[] args) {
System.out.println(binarySearch(new int[] {2, 5, 8, 13, 21}, 13));
}
}📈 Comparison Table
| Complexity | n=10 | n=100 | n=1,000 | n=10,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1,000 | 10,000 |
| O(n log n) | 30 | 700 | 10,000 | 130,000 |
| O(n²) | 100 | 10,000 | 1,000,000 | 100,000,000 |
| O(2ⁿ) | 1,024 | 1.27 × 10³⁰ | ∞ | ∞ |
💡 Cases and bounds are independent
Algorithms can have different complexities depending on input:
- • Best case: Minimum cost among inputs of size n (for example, a match at index 0).
- • Expected/average case: An expectation under a stated probability model, or over an algorithm's random choices.
- • Worst case: Maximum cost among inputs of size n; useful for latency and adversarial guarantees.
Any case can have an O, Ω, or Θ bound. Say “worst-case Θ(n)” rather than using Big-O as shorthand for the case.
Ω, Θ, and O: three lenses
Big-O (upper bound): f(n) is O(g(n)) if beyond some n₀, f(n) ≤ c·g(n). It may describe the best, expected, amortized, or worst-case cost: whichever function f was defined to represent.
Big-Ω (lower bound): f(n) is Ω(g(n)) if f(n) ≥ c·g(n) for large n. A linear scan of an unsorted array to find a specific value is Ω(n) because you may need to read every entry.
Big-Θ (tight bound): f(n) is Θ(g(n)) when it is both O(g(n)) and Ω(g(n)): growth matches g up to constants. Merge sort time is Θ(n log n) in the usual worst-case analysis.
Choose the right input variables
Multi-parameter bounds
Do not collapse independent quantities too early. Graph traversal is Θ(V + E), merging inputs is Θ(n + m), and a hash join can use Θ(n + m) expected time. Writing O(n) hides which input can grow and may be false for sparse or rectangular data.
Output-sensitive bounds
If producing k answers already costs Ω(k), expose it: reporting all matches might be O(n + k). For strings, include character length; comparing or hashing “one item” is not O(1) when the key itself has length L.
Analysis playbook
- Define size and cost: n elements, V/E, key length, comparisons, allocations, I/O, or messages.
- Count sequential work by addition: O(n) followed by O(n log n) is O(n log n).
- Count genuinely nested work by summation: a triangular loop is Σᵢ i = n(n−1)/2, hence Θ(n²).
- Track shrinking/growing loops: repeatedly doubling an index or halving a range takes Θ(log n) steps.
- Write the recurrence: include both recursive subproblems and non-recursive work, then bound depth and work per level.
- State the guarantee: best, worst, expected, amortized, and auxiliary space, plus assumptions.
Amortized analysis
Some operations are usually cheap and occasionally expensive (dynamic array doubling, disjoint-set union with path compression). Amortized cost spreads the rare expensive step over many cheap ones: a sequence of n appends to a doubling vector is O(n) total, so O(1) amortized per append.
Do not confuse amortized with average-case probability: amortized is a worst-case guarantee on long sequences of operations.
Space complexity & hidden memory
Auxiliary space
Extra memory beyond the input (new arrays, hash maps, recursion stack). Merge sort uses O(n) auxiliary space; heap sort can sort in place with O(1) auxiliary but needs random access to mutate the array.
Recursion depth
Each stack frame stores locals and return addresses. A recursion depth of n can mean O(n) stack space even if the heap allocation is small: important for deep trees or naive Fibonacci.
Divide & conquer: Master theorem (sketch)
Many recurrences look like T(n) = a T(n/b) + f(n): a subproblems of size n/b, plus f(n) merge work. The master method compares f(n) with n^(log_b a) to decide which term dominates.
- Merge sort: a=2, b=2, f(n)=Θ(n) → Θ(n log n).
- Binary search on a static structure: a=1, b=2, f(n)=O(1) → Θ(log n).
Full statements have regularity conditions; for interviews, recognizing the three standard cases is enough to predict sorting and tree traversals.
Lower bounds: know when optimization needs a new model
A lower bound proves every algorithm in a specified model must do at least that much work. Finding an arbitrary maximum requires Ω(n) inspections. Comparison sorting requires Ω(n log n) comparisons because a decision tree needs at least n! leaves. Counting and radix sort escape that bound by using integer digits or a bounded key universe: not by performing a better comparison sort.
Lower bounds are model-dependent. Extra preprocessing, randomization, approximation, word-level operations, or a restricted key domain may change the model and make a different bound possible.
From asymptotics to production
| Question | Why it changes the choice |
|---|---|
| Is data in cache, RAM, disk, or remote? | One cache miss or network round trip can dominate thousands of arithmetic operations. |
| What are p50 and p99 inputs? | A great mean can hide a worst-case latency incident or adversarial denial of service. |
| What allocates? | Python objects and slicing add reference/allocation costs; Java boxing adds objects and GC pressure. |
| Is access contiguous? | Cache locality and branch predictability explain why two Θ(n) implementations can differ substantially. |
| Can work run in parallel? | Wall-clock speedup is bounded by the serial fraction and coordination overhead, not only total work. |
Decision rule: first meet the required asymptotic and tail-latency guarantee; then benchmark representative data with warm-up, fixed seeds, multiple sizes, and memory/allocation measurements. Never infer complexity from one timing point.
💼 Production modeling examples
🔍 Index lookup
An inverted index maps a term to a posting list; query cost then depends on dictionary lookup, posting-list lengths, intersections, and ranking, not simply the number of documents in the corpus.
Model with vocabulary size, posting lengths, and output count.
📱 Ranking pipelines
A feed may retrieve candidates, score them, select a top-k subset, and apply business constraints. A heap can select k items in O(n log k), avoiding a full O(n log n) sort when only a small prefix is served.
Model candidate count n, requested results k, and scoring cost.
🎮 Spatial queries
A grid, spatial hash, BVH, or quadtree reduces candidate collision pairs before exact checks. Distribution, object motion, and tree quality determine whether observed work stays near linear or degrades.
Model objects, occupied cells, candidate pairs, and frame budget.
🚗 Route planning
Binary-heap Dijkstra is commonly analyzed as O((V + E) log V), but practical routing also exploits graph structure, heuristics, preprocessing, and changing edge weights. Memory locality can dominate the basic bound.
Model vertices V, edges E, preprocessing, and query latency.
Exercises
- Give an algorithm that is O(n^2) but also O(n^3). Why can both statements be true?
- For binary search, what changes if you count "array reads" vs "wall-clock seconds" on a cold cache?
- Sketch n = 10^5 vs 10^7 for Theta(n), Theta(n log n), and Theta(n^2) operation counts.
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): asymptotic notation chapter.
- Knuth, The Art of Computer Programming: analyzing algorithms and MIX-style cost models.
- Sedgewick & Flajolet, An Introduction to the Analysis of Algorithms.
Short takeaway
Time Complexity = How runtime grows with input size.Big O notation = An asymptotic upper bound on a separately defined cost function.Common classes: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).Key insight: State parameters and guarantees, reject poor scaling, then benchmark the real workload.