2. Algorithm Analysis

Introduction

Algorithm analysis is the process of determining the computational resources required by an algorithm as a function of the input size n. The two primary resources are time (how long the algorithm runs) and space (how much extra memory it uses). Understanding these concepts enables developers to predict performance, compare alternatives, and make informed decisions when designing data structures and algorithms.

Time Complexity

Time complexity measures the number of basic operations an algorithm executes relative to the input size. It is expressed using asymptotic notation, which abstracts away constant factors and lower‑order terms to focus on growth rates.

Common Complexity Classes

Illustrative Examples

1. Accessing a[i]: Direct index calculation yields constant time O(1).
2. Binary Search: Repeatedly halves the search interval → T(n) = T(n/2) + O(1) → solves to O(log n).
3. Linear Search: In the worst case compares each element → T(n) = n → O(n).
4. Bubble Sort: Two nested loops each running up to n → T(n) = Θ(n²).
5. Merge Sort: Recurrence T(n) = 2T(n/2) + Θ(n) → by Master Theorem → Θ(n log n).

Space Complexity

Space complexity quantifies the extra memory an algorithm needs beyond the input data. It includes auxiliary variables, recursion stack space, and any dynamically allocated structures.

Key Concepts

• Auxiliary Space: Memory used temporarily during execution.
• In‑Place Algorithms: Use only O(1) extra space (e.g., heap sort, insertion sort).
• Recursive Space: Each recursive call adds a stack frame; depth determines space usage.

Examples

1. Iterative Factorial: Uses a constant number of variables → O(1) space.
2. Recursive Factorial: Depth of recursion is n → O(n) stack space.
3. Merge Sort (auxiliary array): Requires an extra array of size n → O(n) space.
4. Heap Sort: Operates in‑place → O(1) extra space.

Asymptotic Notations

Asymptotic notations provide a formal way to describe the limiting behavior of functions. The three most common are Big O (upper bound), Big Omega (lower bound), and Big Theta (tight bound).

Definitions

Big O Notation: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

Big Omega Notation: f(n) = Ω(g(n)) if there exist constants c > 0 and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.

Big Theta Notation: f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)) (i.e., tight bound).

Worked Example

Consider T(n) = 3n² + 2n + 1.

• Upper bound: Choose g(n) = n², c = 6, n₀ = 1. Then 3n² + 2n + 1 ≤ 6n² for all n ≥ 1 → T(n) = O(n²).
• Lower bound: Choose g(n) = n², c = 3, n₀ = 1. Then 3n² ≤ 3n² + 2n + 1 → T(n) = Ω(n²).
• Since both hold, T(n) = Θ(n²).

Practical Complexity Analysis

Analyzing an algorithm involves a systematic process: identify the basic operation, count its executions, express the count as a function of n, and simplify using the highest‑order term.

Step‑by‑Step Procedure

1. Identify the basic operation (the operation that dominates runtime, e.g., comparison, assignment).
2. Determine how many times this operation is executed as a function of input size n.
3. Express the total count T(n).
4. Simplify T(n) by keeping only the term with the highest growth rate; discard constants and lower‑order terms.
5. State the result using Big O notation (or Omega/Theta if appropriate).

Example: Linear Search

Basic operation: comparison of the target with an array element.

• Worst case: target absent or at last position → n comparisons → T(n) = n → O(n).
• Best case: target at first position → 1 comparison → T(n) = 1 → Ω(1).
• Average case (assuming uniform distribution): (n+1)/2 → still Θ(n).

Example: Merge Sort (Recurrence Tree)

The algorithm divides the array into two halves, recursively sorts each, then merges them in linear time.

• Recurrence: T(n) = 2T(n/2) + Θ(n).
• Recurrence tree: each level i has 2^i nodes, each costing Θ(n/2^i). Sum over log n levels gives Θ(n log n).
• Using the Master Theorem: a = 2, b = 2, f(n) = Θ(n). Since f(n) = Θ(n^{log_b a}) = Θ(n^{1}), we are in case 2 → T(n) = Θ(n log n).

Tools for Solving Recurrences

• Recurrence Tree Method: visualizes cost per level.
• Substitution Method: guess solution and prove by induction.
• Master Theorem: provides direct solution for recurrences of form T(n) = aT(n/b) + f(n).

Real‑World Relevance

Choosing an algorithm with a lower asymptotic complexity can dramatically affect performance on large datasets.

For sorting one million items:

• An O(n²) algorithm (e.g., insertion sort) may require roughly 10¹² operations — potentially hours or days.
• An O(n log n) algorithm (e.g., merge sort) needs about 20 × 10⁶ operations — often completed in seconds.

Thus, understanding and applying complexity analysis is essential for building scalable software systems.

Summary

This chapter covered:

• Time complexity classes with concrete examples.
• Space complexity considerations, including in‑place and recursive algorithms.
• Formal definitions of Big O, Omega, and Theta notations.
• Practical steps for analyzing algorithms for counting operations and solving recurrences.
• The impact of complexity choices on real‑world performance.

Mastering these concepts equips you to evaluate, compare, and select the most efficient algorithms for any given problem.