Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Algorithm analysis: time and space complexity

Definitions, methods and worked examples for analysing algorithm time and space complexity with Big-O/Θ/Ω, worst/average/best case, step-count, recurrences and Master Theorem, plus common pitfalls and exam tips.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Algorithm analysis tells us how running time and memory grow with input size, so we can predict performance before coding and choose the right data structure or algorithm. In industry, this guides design for web backends, embedded systems with tight RAM, and large data jobs where costs scale with time and space.

Key ideas

  • Input size (n): A measure of the length of input, e.g., number of elements in an array, number of vertices/edges in a graph, number of bits in an integer. Always state what n means before analysis.
  • Basic operation: The step we choose to count (e.g., a comparison, assignment, array access). Assumption: each basic operation takes constant time on the RAM model.
  • RAM model: Abstract machine where arithmetic on fixed-size words, comparisons, and memory access take O(1) time; memory is random-access; no cache effects. Useful for asymptotic analysis.
  • Time complexity T(n): A function that maps input size n to the number of basic operations executed by the algorithm. We often analyze worst, average, and best case.
  • Space complexity S(n): The amount of memory used by an algorithm as a function of n, including input space (sometimes excluded), auxiliary space (extra beyond input), and call stack space for recursion.
  • Asymptotic notation: Formal bounds on functions for large n.
    • Exact statement — Big-O (O): For functions f, g: ℕ→ℝ⁺, f(n) ∈ O(g(n)) iff there exist constants c > 0 and n₀ ≥ 1 such that for all n ≥ n₀, 0 ≤ f(n) ≤ c·g(n). It is an asymptotic upper bound.
    • Exact statement — Big-Ω (Ω): f(n) ∈ Ω(g(n)) iff there exist c > 0 and n₀ ≥ 1 such that for all n ≥ n₀, 0 ≤ c·g(n) ≤ f(n). It is an asymptotic lower bound.
    • Exact statement — Big-Θ (Θ): f(n) ∈ Θ(g(n)) iff there exist c₁, c₂ > 0 and n₀ ≥ 1 such that for all n ≥ n₀, 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n). It is a tight bound.
    • Little-o (o) and little-ω (ω): Strict asymptotic domination: f ∈ o(g) means limₙ→∞ f(n)/g(n) = 0; f ∈ ω(g) means limₙ→∞ f(n)/g(n) = ∞. Often not required in first analysis, but useful to show strictness.
  • Worst-case time: T_worst(n) = max number of basic operations over all inputs of size n.
  • Best-case time: T_best(n) = min number of basic operations over all inputs of size n.
  • Average-case time: Expected number of operations over all inputs of size n under a specified probability distribution on inputs. Always state the distribution (e.g., all permutations equally likely).
  • Amortized analysis: Average cost per operation over a worst-case sequence, not over random inputs. Methods: aggregate method, accounting method (assign credits), potential method (define potential Φ(state)). Assumes an arbitrary but finite sequence of operations.
  • Step-count method: Identify the basic operation(s), write a sum that counts their executions, simplify to a function of n, then give an asymptotic bound using algebra and limits.
  • Common growth rates (faster to slower for time efficiency: left is better):
    • O(1) constant, O(log n) logarithmic (base usually 2; constant factors are ignored), O(n) linear, O(n log n), O(n²) quadratic, O(n³) cubic, O(2^n) exponential, O(n!) factorial.
  • Recurrence relation: An equation that defines T(n) in terms of smaller inputs. Example: T(n) = 2T(n/2) + cn for merge sort. Needs base case like T(1) = d.
  • Master Theorem (divide-and-conquer): For T(n) = a·T(n/b) + f(n), with a ≥ 1, b > 1, and n a power of b for simplicity:
    • Case 1: If f(n) ∈ O(n^{log_b a − ε}) for some ε > 0, then T(n) ∈ Θ(n^{log_b a}).
    • Case 2: If f(n) ∈ Θ(n^{log_b a} · log^k n) with k ≥ 0, then T(n) ∈ Θ(n^{log_b a} · log^{k+1} n).
    • Case 3: If f(n) ∈ Ω(n^{log_b a + ε}) for some ε > 0 and if a·f(n/b) ≤ c·f(n) for some c < 1 and sufficiently large n (regularity condition), then T(n) ∈ Θ(f(n)). Assumptions: divides into a subproblems each of size n/b; combine cost f(n); regularity as stated for Case 3.
  • Substitution method (a.k.a. induction): Guess the form of the solution to a recurrence and prove by induction, adjusting constants to make the inequality hold.
  • Recursion tree method: Expand recurrence level by level, sum cost per level, find number of levels, then sum the series.
  • Space for recursion: Depth of recursion × space per call; add extra arrays if any.
  • Trade-offs: Time vs. space. Example: Hash table with more space gives expected O(1) lookup; or precomputing tables (dynamic programming) uses more space to reduce time.

Diagrams to draw in exam answers (describe):

  • Growth curves: Draw x–y axes. Label x as “n (input size)”, y as “time (steps)”. Plot and label separate curves for log n, n, n log n, n², 2^n. Ensure that for large n, 2^n is above all, n² above n log n, which is above n, which is above log n.
  • Recursion tree: Draw a root with cost f(n) written next to it. Children show a subproblems with sizes n/b, each node labeled with its local cost. Draw depth as log_b n levels. Sum costs per level on the right side and show final sum at bottom.
  • Stack growth: Boxes stacked vertically labeled “frame for n”, “n−1”, ..., down to base. Annotate each frame with local variables size and return address to show space per call and total depth.

Exact derivations universities commonly ask for (step-by-step sketches):

  1. Nested loops step-count: For code with outer loop i = 1..n and inner loop j = 1..i, count inner body once per j. Total counts = Σ_{i=1..n} Σ_{j=1..i} 1 = Σ_{i=1..n} i = n(n+1)/2 → Θ(n²).
  2. Deriving merge sort time: T(n) = 2T(n/2) + cn, T(1) = d. Recursion tree has log₂ n levels. Work per level: cn. Total work: cn log₂ n + d·n (leaf contributions fold into Θ(n)). Thus T(n) ∈ Θ(n log n).
  3. Exponential recursion (Fibonacci naive): T(n) = T(n−1) + T(n−2) + O(1) yields T(n) ∈ Θ(φ^n), where φ ≈ 1.618, via characteristic equation or lower-bounding by T(n−1) + T(n−2) ≥ T(n−1) leading to growth with base > 1.

Formulas

  • f(n) ∈ Ω(g(n)) ⇔ ∃ c > 0, n₀ ≥ 1 : ∀ n ≥ n₀, 0 ≤ c·g(n) ≤ f(n) — Lower bound definition.
  • f(n) ∈ Θ(g(n)) ⇔ ∃ c₁, c₂ > 0, n₀ ≥ 1 : ∀ n ≥ n₀, 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) — Tight bound definition.
  • T(n) = a·T(n/b) + f(n) — Divide-and-conquer recurrence, where a is number of subproblems, b is shrink factor, f(n) is combine cost; use Master Theorem if conditions hold.
  • log_b a = ln a / ln b — Change of base for logs; no units; useful in Master Theorem.
  • Σ_{i=1..n} i = n(n+1)/2 — Arithmetic series; steps counted for triangular nested loops; unit: operations (dimensionless in RAM model).
  • Σ_{i=0..k} r^i = (r^{k+1} − 1)/(r − 1) (r ≠ 1) — Geometric series; used in recursion-tree sums.
  • space_recursion = depth × space_per_call — Stack space estimate; units: bytes.
  • amortized_cost = (total_cost over sequence) / (number of operations) — Aggregate method; units: operations per op.

Worked examples

Example 1 — Step-count and tight bound for nested loops Question: Find the exact count of comparisons and the time complexity for the following code segment. Assume each comparison of j <= i and i <= n counts as 1 operation; the body executes a single comparison a[j] < key.

for i in range(1, n+1): j = 1 while j <= i: if a[j] < key: pass j += 1

Model answer:

  1. Identify basic operations: comparisons in while (j ≤ i) and if (a[j] < key). Initialization and increments can be included but do not change Θ-bound; we count them to get exact sum.
  2. Outer loop control: i runs from 1 to n inclusive. That loop condition i ≤ n is checked n+1 times and increment done n times. We focus on inner costs per i.
  3. For fixed i, inner while runs i+1 times for the condition check (true i times, false once) and the if comparison runs i times.
  4. Total comparisons across all i:
    • While-condition checks: Σ_{i=1..n} (i + 1) = Σ i + Σ 1 = n(n+1)/2 + n = (n² + n)/2 + n = (n² + 3n)/2.
    • If comparisons: Σ_{i=1..n} i = n(n+1)/2 = (n² + n)/2.
    • Grand total comparisons = (n² + 3n)/2 + (n² + n)/2 = (2n² + 4n)/2 = n² + 2n.
  5. Therefore, exact comparison count = n² + 2n; asymptotically T(n) ∈ Θ(n²). Best, average, worst are the same here as the number of iterations is data-independent.

Example 2 — Solve a recurrence by Master Theorem Question: Solve T(n) = 3·T(n/2) + n, with T(1) = 1. Give Θ-bound and brief justification.

Model answer:

  1. Identify a, b, f(n): a = 3, b = 2, f(n) = n.
  2. Compute n^{log_b a}: log₂ 3 ≈ 1.585. So n^{log₂ 3} ≈ n^{1.585}.
  3. Compare f(n) to n^{log₂ 3}: f(n) = n ∈ O(n^{1.585−ε}) with ε ≈ 0.585 > 0.
  4. Master Theorem Case 1 applies. Therefore, T(n) ∈ Θ(n^{log₂ 3}).
  5. Base case T(1) is constant, satisfying assumptions. Final bound: T(n) ∈ Θ(n^{log₂ 3}).

Example 3 — Space complexity of merge sort (including recursion stack and auxiliary arrays) Question: Determine the space complexity (auxiliary space) of merge sort on an array of length n, assuming the merge step uses a temporary array of size equal to the subarray being merged, and recursion uses the call stack. State the total auxiliary space S(n).

Model answer:

  1. Each merge of two halves of total length m allocates a temporary array of size m (bytes proportional to m elements). Across recursion, allocations do not overlap across levels because each call first recurses; then, during its merge, it allocates a temporary array and frees it before returning. However, within a single call’s merge, the maximum temporary size is n at the top level.
  2. Recursion stack depth: splitting halves until size 1 gives depth ⌈log₂ n⌉. Each stack frame stores a constant amount of info (like two indices and a few pointers) ⇒ O(1) words per frame, so total stack space O(log n) words.
  3. Dominant space: the temporary array used during each merge at the current level can be up to n elements. Even though there are multiple merges per level, they do not overlap in time within a single call path; the maximum simultaneous temp storage is O(n).
  4. Therefore, auxiliary space S(n) = O(n) for the temporary array plus O(log n) for recursion stack. Since O(n) dominates O(log n), the total auxiliary space is S(n) ∈ O(n). If we exclude the input array itself from auxiliary space, answer remains O(n).

Example 4 — Amortized analysis of dynamic array push Question: Show that push (append) on a dynamic array that doubles its capacity when full has O(1) amortized time per operation.

Model answer (aggregate method):

  1. Cost model: Inserting into non-full array costs 1 (write). When full, resizing from capacity c to 2c costs c (to copy c elements) + 1 (to write new element) = c + 1.
  2. Consider a sequence of m pushes starting from empty array with capacity 1. Total cost is the sum of unit inserts plus occasional expansions.
  3. Number of expansions is ⌊log₂ m⌋ when starting from capacity 1 and performing m ≥ 1 pushes (capacities double: 1, 2, 4, … ≤ m). The total number of elements copied over all expansions is 1 + 2 + 4 + … < m, so it is < 2m.
  4. Add the m writes themselves: m. So total cost < (2m − 1) + m < 3m.
  5. Amortized cost per push = total/m < 3m/m = 3 = O(1). Thus, append has O(1) amortized time.

Common mistakes

  • Counting the wrong basic operation: For search, comparisons matter; for matrix multiply, scalar multiplications dominate. Say what you count.
  • Mixing worst and average case: Writing “average case O(n)” without specifying distribution, or giving worst-case bound when asked average.
  • Dropping dominant terms incorrectly: Saying n + log n = O(log n). Correct is O(n). Always keep the fastest-growing term’s coefficient for Big-Θ and drop lower-order terms only after comparing growth.
  • Misusing asymptotic notation: Writing f(n) = O(g(n)) as if it were equality, or saying “O(n) = n²”. Correct phrasing: “f(n) ∈ O(n²)” or “T(n) is O(n²)”.
  • Ignoring loop bounds: Off-by-one errors in sums (e.g., inner loop runs i times, but you count i+1 or i−1 wrongly). Write small n tables (n=1,2,3) to check pattern.
  • Applying Master Theorem blindly: Using it when a or b are not constants, or when f(n) is irregular (e.g., n/log n) without checking Case 3 regularity condition.
  • Forgetting recursion stack space: Reporting only array temporaries and ignoring O(depth) stack frames.
  • Assuming base of log matters asymptotically: log₂ n and log₁₀ n differ by a constant factor; for Big-O/Θ they are equivalent. State base if exact constants are asked.
  • Confusing amortized with average: Amortized is over worst-case sequence of operations; average is expectation over input distribution.

For your exam

  • Short notes: RAM model assumptions; common growth orders; time–space trade-offs with one example (e.g., memoization vs recomputation).
  • Derivations: Step-count for nested loops; sum of series; proving Θ-bounds via inequalities; solving a recurrence (Master Theorem, substitution, recursion tree). Show each step and justify the case selection.
  • Theory long answer: Compare worst/average/best for a search (linear or binary) including distributions; explain amortized analysis for dynamic array with clear cost summation; or prove a bound for Quick sort’s expected time (outline only, full proof belongs to Sorting topic but you can cite result).
  • Diagrams: Growth curves; recursion tree; call stack. Label axes, levels, sizes, and per-level costs.
  • What earns full marks: Clear definition of n and basic operation; correct sums with bounds; correct application of asymptotic notation with constants where needed; correct selection and justification of Master Theorem case; neat labeled diagrams as asked; final Θ-bound stated clearly.

Quick check

  1. State the formal definition of f(n) ∈ Θ(g(n)).
  2. For T(n) = 2T(n/2) + n/log n, which Master Theorem case applies? Justify briefly.
  3. What is the auxiliary space of a recursive DFS on a graph with n vertices and maximum recursion depth d (no parent array beyond visited)?

Answers: 1) ∃ c₁, c₂ > 0 and n₀ ≥ 1 such that ∀ n ≥ n₀, 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n). 2) None of the standard Master Theorem cases apply because f(n) = n/log n is neither O(n^{1−ε}) nor Θ(n log^k n) for any k ≥ 0; using a recursion tree (or Akra–Bazzi), T(n) = Θ(n log log n). 3) O(n) for the visited array plus O(d) for the recursion stack, so auxiliary space O(n + d) = O(n).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?