Time and space complexity

In short

Time and space complexity measure how the running time and memory of an algorithm grow as the input size n grows, written in asymptotic notation (O, Ω, Θ) that ignores machine speed and constant factors. It is the single most examined idea in algorithms: every GATE CSE paper carries questions on loop counting, recurrences and asymptotic comparison, and every coding round at Amazon, Microsoft, Google, Flipkart, Zoho, Adobe, Oracle, Samsung R&D and the service majors (TCS NQT, Infosys, Wipro) asks "what is the complexity of your solution?" before accepting it. On Indian judges (CodeChef, HackerEarth, HackerRank) complexity decides whether code passes within the 1-second limit or gets TLE. It is also the language in which tractability is defined — the classes P, NP and NP-complete.

Explained

What is measured, and why asymptotically

• Input size n: number of elements for arrays and lists, number of vertices and edges (V, E) for graphs, length for strings; for arithmetic algorithms the size is the number of bits, which is why a loop to n is exponential in the bit length of n.
• Cost model: the RAM model — each arithmetic, comparison, assignment and array access on a word-sized value costs 1 unit; time complexity T(n) counts these primitive operations.
• Actual seconds depend on CPU, compiler, cache and language, so they are not comparable; the order of growth is machine-independent and predicts behaviour at large n.
• Constants and lower-order terms are dropped: 3n² + 50n + 700 is Θ(n²), because for large n the n² term dominates.
• Limitation: asymptotics hide constants, so an O(n log n) algorithm with a huge constant can lose to an O(n²) one on small n — this is why library sorts switch to insertion sort for small subarrays.

Asymptotic notations and their properties

• Big-O (upper bound): f(n) = O(g(n)) if f grows no faster than g. Used for worst-case guarantees.
• Big-Omega (lower bound): f(n) = Ω(g(n)) — f grows at least as fast as g.
• Big-Theta (tight bound): f(n) = Θ(g(n)) if f = O(g) and f = Ω(g). This is the exact order of growth.
• little-o: f = o(g) if f is strictly smaller in growth — lim f/g = 0 (n → ∞). n = o(n²), n ≠ o(n).
• little-omega: f = ω(g) if lim f/g = ∞. n² = ω(n).
• Properties: transitive (all five); O and Ω are reflexive, Θ is reflexive, symmetric and transitive (an equivalence relation); f = O(g) ⟺ g = Ω(f); O(f + g) = O(max(f, g)); c·O(f) = O(f); O(f)·O(g) = O(f·g).
• Base of logarithm is irrelevant: log_b n = log₂n / log₂b, a constant factor, so all are Θ(log n). But the base of an *exponent* matters: 2ⁿ ≠ Θ(3ⁿ).
• Limit rule: compare f and g by lim f/g — 0 ⇒ f = o(g), finite non-zero c ⇒ f = Θ(g), ∞ ⇒ f = ω(g). L'Hôpital's rule helps (e.g. log n vs n^0.5).
• Standard growth order (slowest to fastest): 1 < log log n < log n < (log n)^k < n^ε < √n < n < n log n < n² < n³ < nᵏ < 2ⁿ < 3ⁿ < n! < nⁿ.
• Polynomial beats exponential always; any polylog beats any positive power of n.

Best, worst, average case — and amortized

• Worst case: maximum operations over all inputs of size n. Default in interviews and exams because it is a guarantee. Linear search: Θ(n).
• Best case: minimum over inputs — linear search Θ(1) when the key is first. Rarely useful alone.
• Average case: expected operations under an assumed input distribution (usually uniform). Linear search with the key present: (n+1)/2 comparisons ⇒ Θ(n). Quicksort: Θ(n log n) average, Θ(n²) worst.
• Amortized: average cost per operation over a *worst-case sequence* of m operations — no probability assumed. Three techniques:
  1. Aggregate method: find total cost of m operations, divide by m.
  2. Accounting (banker's) method: charge each operation a fixed amortized price; surplus is stored as credit on data-structure elements to pay for later expensive operations.
  3. Potential method: define Φ ≥ 0 on the structure; amortized cost = actual cost + ΔΦ. Choose Φ so every amortized cost is small.
• Classic amortized results: dynamic array (vector/ArrayList) push_back O(1) amortized by doubling; incrementing a binary counter O(1) amortized per increment; union-find with union by rank + path compression O(α(n)) ≈ O(1) amortized; splay tree operations O(log n) amortized.
• Amortized ≠ average: amortized is a worst-case-sequence guarantee with no randomness; average case depends on an input distribution.

Analysing iterative code — counting rules

• Sequence: add the costs, keep the maximum. Nesting: multiply. If-else: take the worst branch (for Big-O).
• Simple loop for i=1 to n → Θ(n); two independent loops → Θ(n), not Θ(n²).
• Triangular nesting for i=1..n { for j=1..i } → 1+2+…+n = n(n+1)/2 → Θ(n²).
• Multiplicative counter for (i=1; i<=n; i=i*2) → Θ(log n) (i takes values 1,2,4,… up to n). Similarly while(n>1) n = n/2 → Θ(log n).
• Nested with a doubling inner loop → Θ(n log n); for (i=1; i*i<=n; i++) → Θ(√n).
• Harmonic nesting for (i=1; i<=n; i++) for (j=1; j<=n; j+=i) → n(1 + 1/2 + … + 1/n) = n·H_n → Θ(n log n).
• Doubly logarithmic for (i=2; i<=n; i=i*i) → Θ(log log n).
• Count the number of times the innermost statement executes, as a function of n, then take Θ.

Analysing recursive code — recurrences

• Write T(n) = (cost of recursive calls) + (work outside the calls), with a base case T(1) = Θ(1). Also count the recursion stack for space: depth × frame size.
• Substitution / iteration method: expand repeatedly, spot the pattern, sum. T(n) = T(n−1) + n → n + (n−1) + … + 1 = Θ(n²). T(n) = T(n−1) + 1 → Θ(n). T(n) = 2T(n−1) + 1 → Θ(2ⁿ).
• Recursion tree method: draw levels, compute cost per level, multiply by depth (or sum a geometric series). Useful when levels are unequal, e.g. T(n) = T(n/3) + T(2n/3) + n → Θ(n log n).
• Master theorem for T(n) = a·T(n/b) + f(n), a ≥ 1, b > 1: compare f(n) with n^{log_b a}.
  • Case 1: f(n) = O(n^{log_b a − ε}) ⇒ T(n) = Θ(n^{log_b a}) — leaves dominate.
  • Case 2: f(n) = Θ(n^{log_b a}·logᵏn), k ≥ 0 ⇒ T(n) = Θ(n^{log_b a}·log^k+1n) — balanced.
  • Case 3: f(n) = Ω(n^{log_b a + ε}) and a·f(n/b) ≤ c·f(n) for some c < 1 ⇒ T(n) = Θ(f(n)) — root dominates.
  • It does not apply when a or b is not constant, when f is not asymptotically positive, or when f oscillates (e.g. T(n) = 2T(n/2) + n/log n falls in a gap).
• Masters theorem for subtract-and-conquer: T(n) = a·T(n−b) + f(n) → Θ(n·f(n)) if a = 1, and Θ(n^k · a^n/b) if a > 1 with f(n) = n^k.
• Akra–Bazzi handles unequal splits (beyond most undergraduate syllabi; mentioned in advanced electives).

Space complexity

• Space complexity = input space + auxiliary space. Interviewers almost always mean auxiliary (extra) space — everything beyond the input itself.
• In-place algorithm: O(1) auxiliary space (heapsort, insertion sort, reversal of an array, Dutch national flag partition). Merge sort needs Θ(n) auxiliary; recursive quicksort needs Θ(log n) stack on average and Θ(n) in the worst case (Θ(log n) worst case if you recurse on the smaller side and loop on the larger).
• Recursion stack is space: a recursion of depth d with constant-size frames costs Θ(d). Naive recursive Fibonacci is Θ(φⁿ) ≈ Θ(1.618ⁿ) time (loosely quoted as O(2ⁿ)) but only Θ(n) space, because only one root-to-leaf path is live at a time.
• Typical figures: adjacency matrix Θ(V²) vs adjacency list Θ(V + E); BFS queue Θ(V); DP table for 0/1 knapsack Θ(nW), reducible to Θ(W) by keeping one row.
• Time–space tradeoff: memoisation, hash tables, precomputed sieves, lookup tables and prefix sums buy speed with memory; recomputing values saves memory at the cost of time. Rolling-array DP is the standard exam example.
• Savitch's theorem (theory electives): NSPACE(s) ⊆ DSPACE(s²); space classes L, NL, PSPACE appear in GATE theory-of-computation questions rather than in the algorithms paper.

Complexity classes and intractability

• Tractable: solvable in polynomial time, O(n^k) for constant k — the class P.
• NP: problems whose *proposed solution* can be verified in polynomial time by a deterministic machine (equivalently, solved in polynomial time by a non-deterministic one). P ⊆ NP; whether P = NP is open.
• NP-hard: at least as hard as every problem in NP, i.e. every NP problem reduces to it in polynomial time. Need not be in NP, need not be a decision problem.
• NP-complete: in NP and NP-hard — the hardest problems inside NP. SAT was the first (Cook–Levin theorem); others include 3-SAT, clique, vertex cover, Hamiltonian cycle, subset-sum, graph colouring and the decision form of TSP.
• Polynomial-time reduction A ≤_p B: if B is easy then A is easy; used to *prove* hardness (reduce a known NP-complete problem to the new one).
• Pseudo-polynomial: 0/1 knapsack DP runs in O(nW) — polynomial in the *value* W but exponential in the number of bits of W, so knapsack remains NP-complete.
• Coping with intractability: approximation algorithms, heuristics, branch and bound, parameterised algorithms, randomisation, or restricting the input class.
• Lower bounds: comparison-based sorting and searching are Ω(n log n) and Ω(log n) respectively in the decision-tree model — a bound on the *problem*, not on one algorithm.

Key points

• Time complexity - count of primitive operations as a function of input size, in the RAM model.
• Space complexity - total memory = input + auxiliary; "extra space" means auxiliary only.
• Big-O - upper bound (at most); Ω - lower bound (at least); Θ - tight bound (exactly this order).
• little-o / little-ω - strict bounds; lim f/g = 0 or ∞ respectively.
• Drop constants and lower terms - 5n² + 100n + 9 = Θ(n²); O(max) rule for sums.
• Log base is irrelevant inside Θ(log n); exponent base is not.
• Worst case is the default guarantee; average case needs an input distribution; amortized averages over a worst-case operation sequence.
• Nesting multiplies, sequence adds - the innermost statement count is the answer.
• Multiplying/dividing counter ⇒ log n; i*i<=n ⇒ √n; triangular nesting ⇒ n².
• Master theorem - compare f(n) with n^{log_b a} for T(n) = aT(n/b) + f(n).
• Recursion tree gives per-level cost × depth; substitution suits T(n) = T(n−1) + f(n).
• Recursion depth is space - stack frames count even when nothing is allocated.
• In-place = O(1) auxiliary space; heapsort is, merge sort is not.
• Amortized O(1) - dynamic array doubling, binary counter increment, union-find with rank + path compression.
• Time–space tradeoff - memoisation and lookup tables trade memory for speed.
• P - polynomial-time solvable; NP - polynomial-time verifiable; NP-complete - in NP and NP-hard; NP-hard - as hard as all of NP.
• Comparison sorting is Ω(n log n) - a decision-tree lower bound on the problem itself.
• Practical rule - about 10⁸ simple operations per second, so fit the algorithm to n before coding.

Formulas and examples

Symbols: n = input size, c, c₁, c₂ = positive constants, n₀ = threshold beyond which the bound holds, a = number of subproblems, b = shrink factor, f(n) = work outside the recursive calls, γ = Euler–Mascheroni constant. Units are *operations* (time) and *words or bytes* (space) — not seconds, because seconds are machine-dependent.

Example 1 — prove a bound from the definition. Show 3n² + 10n + 5 = Θ(n²).

• Upper: for n ≥ 1, 3n² + 10n + 5 ≤ 3n² + 10n² + 5n² = 18n², so c₂ = 18, n₀ = 1.
• Lower: 3n² + 10n + 5 ≥ 3n², so c₁ = 3.
• With c₁ = 3, c₂ = 18, n₀ = 1 both inequalities hold ⇒ Θ(n²). (It is also O(n³) — true but not tight.)

Example 2 — loop counting.

int c = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        c++;

• Inner loop for a given i runs ⌈n/i⌉ ≈ n/i times.
• Total ≈ n(1 + 1/2 + 1/3 + … + 1/n) = n·H(n) ≈ n(ln n + 0.5772).
• For n = 1000: H(1000) ≈ 7.485, so c ≈ 1000 × 7.485 ≈ 7,485 ⇒ Θ(n log n), not Θ(n²).

Example 3 — recurrence by recursion tree and by master theorem. T(n) = 2T(n/2) + n, T(1) = 1, n = 8.

• Level 0: one node, cost 8. Level 1: two nodes × 4 = 8. Level 2: four × 2 = 8. Level 3: eight leaves × 1 = 8.
• Depth = log₂8 = 3, so levels = 4, each costing n = 8 ⇒ total = 4 × 8 = 32 = n(log₂n + 1).
• Master theorem: a = 2, b = 2, log_b a = 1, f(n) = n = Θ(n¹) ⇒ Case 2 with k = 0 ⇒ Θ(n log n). Space = recursion depth = Θ(log n).

Example 4 — master theorem, all three cases.

(log₄3 = 0.7925, log₂7 = 2.8074.)

Example 5 — amortized cost of a doubling dynamic array. Capacity starts at 1 and doubles when full; a copy costs 1 per element.

• Insert 16 elements: 16 writes, plus copies when capacity grows 1→2, 2→4, 4→8, 8→16, costing 1 + 2 + 4 + 8 = 15.
• Total = 16 + 15 = 31 operations for 16 inserts ⇒ 1.94 per insert.
• In general total ≤ n + (2n − 1) < 3n, so amortized cost is O(1) even though a single insert can cost Θ(n).

Example 6 — choosing an algorithm from n (≈10⁸ operations per second).

So for n = 10⁵ an O(n²) solution needs about 100 s and gets TLE, while O(n log n) needs 1.7×10⁶ operations ≈ 0.017 s. Binary search on n = 10⁶ takes ⌈log₂10⁶⌉ = 20 comparisons against 10⁶ for linear search.

Where it is used

• Product engineering interviews and hiring: Amazon, Microsoft, Google, Adobe, Flipkart, Swiggy, Zomato, Zoho, Samsung R&D and Oracle reject accepted-logic answers that miss the complexity target; stating time and space is part of the expected answer.
• Competitive programming and assessment platforms: CodeChef, HackerEarth, HackerRank and TCS CodeVita set constraints (n ≤ 10⁵, 10⁶) precisely to force a particular complexity class; TLE/MLE verdicts are complexity failures.
• Backend and database work: query plan costs (nested-loop vs hash vs merge join), index choice (B-tree O(log n) lookups vs full scan O(n)), cache sizing and pagination design at Paytm, PhonePe, Razorpay-scale transaction volumes.
• Embedded and firmware roles: memory is the binding constraint on microcontrollers, so O(1)-space in-place algorithms and fixed-size buffers are mandatory; auxiliary space is reviewed as strictly as time.
• Data science and ML engineering: training cost in terms of samples and features (e.g. O(n·d) per epoch), inference latency budgets, and choosing approximate nearest-neighbour search over exact O(n·d) scans.
• Exams and admissions: GATE CSE (asymptotic comparison, loop counting, recurrences, NP-completeness), UGC-NET, ISRO/BARC/DRDO and PSU written tests, and university Design and Analysis of Algorithms papers under the AICTE model curriculum.

Interview questions

• Q: What is the difference between O, Θ and Ω? A: O is an upper bound, Ω a lower bound and Θ a tight bound holding both ways; saying an algorithm is O(n³) when it is Θ(n²) is correct but uninformative.
• Q: Is it correct to say merge sort is O(n²)? A: Technically yes, since O is only an upper bound, but it is a loose bound — the tight answer is Θ(n log n).
• Q: Why do we drop constants and lower-order terms? A: Constants depend on the machine and compiler, and for large n the highest-order term dominates, so the order of growth is the machine-independent comparison.
• Q: Does the base of the logarithm matter in O(log n)? A: No — changing base multiplies by a constant (log_b n = log₂n/log₂b), so all bases give Θ(log n); the base of an exponential does matter.
• Q: What is the complexity of for (i = 1; i <= n; i = i * 3)? A: Θ(log n), because i takes about log₃n values before exceeding n, and log₃n = Θ(log n).
• Q: What is amortized analysis, and how does it differ from average-case? A: Amortized analysis averages the cost over a worst-case sequence of operations with no probabilistic assumption; average case averages over a probability distribution of inputs.
• Q: Naive recursive Fibonacci — time and space? A: Θ(φⁿ) ≈ Θ(1.618ⁿ) time (often loosely quoted as O(2ⁿ)), but only Θ(n) space, because the stack holds just one root-to-leaf path at a time.
• Q: Quicksort's space complexity? A: Θ(1) auxiliary for partitioning, but Θ(log n) average and Θ(n) worst-case recursion stack; recursing on the smaller partition first bounds the stack at Θ(log n).
• Q: Is 2ⁿ⁺¹ = O(2ⁿ)? Is 2²ⁿ = O(2ⁿ)? A: The first is yes (2ⁿ⁺¹ = 2·2ⁿ, a constant factor); the second is no, since 2²ⁿ/2ⁿ = 2ⁿ → ∞.
• Q: Why is 0/1 knapsack still NP-complete if DP solves it in O(nW)? A: W is a numeric value, not the input length; W needs log W bits, so O(nW) is exponential in the input size — it is pseudo-polynomial.
• Q: Difference between NP-hard and NP-complete? A: NP-complete problems are in NP and NP-hard; NP-hard problems are at least as hard as everything in NP but need not belong to NP (for example the halting problem, or optimisation versions).
• Q: How do you decide the required complexity before coding? A: From the constraints — about 10⁸ operations per second means n ≤ 10⁴ allows O(n²), n up to 10⁶ needs O(n log n) or O(n), and n ≤ 20–25 permits O(2ⁿ).
• Q: Give an example of a time–space tradeoff you have used. A: Memoising a recursive DP turns exponential time into Θ(states) time at the cost of a Θ(states) table; a prefix-sum array costs Θ(n) memory to answer range-sum queries in O(1) instead of O(n).

Common mistakes

• Writing Big-O when a tight bound is wanted, or claiming "best case is O(…) and worst case is Ω(…)" — notation and case are independent axes; any case can be described with O, Ω or Θ.
• Adding instead of multiplying for nested loops (or vice versa), and assuming every nested loop is n² — a doubling or j += i inner loop makes it n log n.
• Forgetting the recursion stack when reporting space, and so calling a recursive traversal "O(1) space".
• Applying the master theorem to T(n) = T(n−1) + n, or to non-constant a and b, instead of using substitution.
• Mixing up n and the bit length of n, which makes trial-division primality look polynomial.
• Treating amortized O(1) as worst-case O(1) — a single dynamic-array insert or a single hash-table insert during rehashing can cost Θ(n).
• Ignoring hidden costs inside library calls: string concatenation in a loop, list.insert(0, x), substring copies, or using an O(n) in test on a list instead of an O(1) set.
• Comparing two algorithms by measured seconds on one small input and concluding one has a better complexity.

Related topics

Sorting algorithms · Searching and binary search · Recursion and backtracking · Divide and conquer · Dynamic programming · DSA interview patterns