Detailed Time Complexity Analysis

While Big-O notation gives us a high-level bound, we often need a more granular way to calculate the exact workload of an algorithm. Two common techniques are the Step-Count Method and the Frequency-Count Method.

1. The Frequency-Count Method

This involves counting how many times each statement in the algorithm is executed as a function of $n$.

Example: Matrix Addition

1void add(int n, int A[][n], int B[][n], int C[][n]) {
2    for (int i = 0; i < n; i++) {           // (1)
3        for (int j = 0; j < n; j++) {       // (2)
4            C[i][j] = A[i][j] + B[i][j];    // (3)
5        }
6    }
7}

Asymptotic Result: $T(n) = O(n^2)$

2. The Step-Count Method

Instead of lines, we assign a "step" value to each type of operation (assignment = 1, comparison = 1, return = 1). We then sum these up.

Space Complexity Breakdown

Space complexity isn't just about the size of the input array. It consists of:

1. Instruction Space: The amount of memory used to store the compiled version of the instructions (code).
2. Data Space: Memory used to store constants and simple variables.
3. Stack Space: Crucial for recursive algorithms. Every recursive call adds a "frame" to the stack containing local variables and the return address.

Formula: $S(P) = c + S_p(n)$ Where $c$ is the fixed part (constants, code) and $S_p(n)$ is the variable part dependent on input size.

The Time-Space Trade-off: Strategic Decisions

The "Time-Space Trade-off" is a fundamental principle in algorithm design: To reduce the time required by an algorithm, you often need to increase the memory it uses, and vice versa.

Case Study 1: Memoization (Space for Time)

In a naive recursive Fibonacci calculation, we recompute the same values thousands of times.

• Naive Recursive: $T(n) = O(2^n)$, $S(n) = O(n)$ (stack).
• Memoized (DP): We store results in an array. $T(n) = O(n)$, $S(n) = O(n)$ (extra array). We sacrifice $O(n)$ space to drop the time from exponential to linear.

Case Study 2: Lookup Tables

Imagine an algorithm that needs to calculate the number of set bits (1s) in a 32-bit integer.

• Approach A (Time Intensive): Loop 32 times, checking each bit. $O(1)$ extra space, but slow.
• Approach B (Space Intensive): Precompute the set bits for all numbers from 0-255 and store them in an array of size 256. To check a 32-bit number, just do 4 array lookups.
• Trade-off: We use 256 bytes of memory to significantly speed up every calculation.

Case Study 3: Compressed Data (Time for Space)

In systems with very limited memory (like embedded sensors), we might store data in a compressed format.

• Benefit: Uses significantly less space.
• Cost: Every time we need to read the data, we must run a decompression algorithm, which consumes CPU time.