Performance Analysis: Space and Time Complexity

Performance analysis is a fundamental aspect of algorithm design, allowing us to quantitatively evaluate and compare the efficiency of different solutions to a problem. This topic explores the core concepts of space and time complexity, which are essential metrics for understanding an algorithm's resource consumption.

1. What is Performance Analysis?

Performance analysis is the process of estimating the amount of computer memory and time an algorithm needs to execute and produce a desired result. The primary goal is to develop a robust skill for evaluating and making informed judgments about the suitability and efficiency of algorithms for various computational tasks.

Performance analysis is typically done using two key metrics:

Time complexity: How much time an algorithm takes to run.
Space complexity: How much memory an algorithm needs to run.

2. Space Complexity

Space complexity quantifies the total amount of auxiliary memory an algorithm requires to run to completion. It represents the memory footprint of the algorithm, measured as a function of the input size.

The space requirement for any algorithm can be broken down into two main components:

Fixed part ( $C$ ): This portion is independent of the characteristics of the input and output. It includes:
- Instruction space: The memory required to store the compiled code of the algorithm itself.
- Space for simple variables and constants used in the algorithm.
Variable part ( $S_P(instance)$ ): This portion consists of the space needed by variables whose size is dependent on the specific instance of the problem being solved (e.g., input size, recursion stack space).

Thus, the total space complexity $S(P)$ for a program $P$ can be expressed as: $S(P) = C + S_P(instance)$

Let's look at an example to illustrate space complexity:

Example 1: Simple Arithmetic Function Consider an algorithm for a simple arithmetic operation:

plaintext

Algorithm abc(a, b, c)
{
  return a + b * c + (a + b - c);
}

In this case, memory is required to store variables a, b, and c. Assuming each takes 1 'Word' of memory:

a: 1 Word
b: 1 Word
c: 1 Word

The space required is effectively a constant, $S(P) = 3$ Words. This is independent of any input "size" in the traditional sense. So, its space complexity would be $O(1)$ .

Example 2: Summing $n$ Elements in an Array Now, consider an algorithm to sum $n$ elements in an array:

plaintext

Algorithm sum(a, n)
{
  S = 0.0;
  for i = 1 to n do
  {
    S = S + a[i];
  }
  return S;
}

To calculate the space complexity:

Space for array a[]: $n$ Words (depends on input size $n$ )
Space for variable n: 1 Word (fixed)
Space for variable S: 1 Word (fixed)
Space for loop counter i: 1 Word (fixed)

So, $S_P(instance) = n$ (for array a). The fixed part $C = 1 + 1 + 1 = 3$ (for , , ). Therefore, the total space complexity is . As becomes very large, the constant becomes negligible. So, the space complexity is approximately proportional to , which is .

3. Time Complexity

Time complexity refers to the amount of computational time an algorithm takes to produce the desired result. It is typically the sum of the compile time and the run (or execution) time. In performance analysis, we primarily focus on run-time because:

Compile time is generally independent of the input characteristics and is a one-time cost.
Once compiled, a program can run many times without recompilation.

The run-time of an algorithm depends on several factors, including:

Input size.
Quality of the code generated by the compiler.
Speed of the machine's processor.
Time complexity of the algorithm itself.

To abstract away machine-dependent factors, we often count the number of basic operations or "steps" an algorithm performs as a function of its input size.

Methods to Compute Step Count:

Introducing a new variable count: Increment a count variable for each basic operation. This is mostly a theoretical approach for deriving the step function.
Frequency Table (Tabular Method): Assign a "steps per execution" (s/e) value to each line of code and multiply it by its "frequency" (number of times it executes) to get the "total steps" for that line. Summing these totals gives the overall step count.

Example: Summing $n$ Elements in an Array (Time Complexity)

Let's re-analyze the sum algorithm using the frequency table method:

plaintext

Algorithm Sum(a, n)
{
  S = 0.0;             // Line 1
  for i = 1 to n do    // Line 2 (loop condition)
  {
    S = S + a[i];    // Line 3
  }
  return S;            // Line 4
}

| Statement | s/e | Frequency | Total Steps | | :------------------ | :-- | :----------- | :---------- | | S = 0.0; | 1 | 1 | 1 | | for i = 1 to n do | 1 | $n+1$ | $n+1$ | | S = S + a[i]; | 1 | $n$ | $n$ | | return S; | 1 | 1 | 1 | | | | | |

The total number of steps is $2n+3$ . As $n$ grows, the dominant term is $2n$ . We drop constants and lower-order terms when expressing time complexity, so the time complexity is $O(n)$ .

Example: Matrix Addition (Time Complexity) Consider an algorithm for matrix addition for two $rows \times cols$ matrices:

plaintext

Algorithm add(a, b, c, rows, cols)
{
  int i, j;
  for (i = 0; i < rows; i++)        // Line 1
    for (j = 0; j < cols; j++)      // Line 2
      c[i][j] = a[i][j] + b[i][j];  // Line 3
}

| Statement | s/e | Frequency | Total Steps | | :----------------------------- | :-- | :-------------------- | :-------------------- | | for (i = 0; i < rows; i++) | 1 | $rows+1$ | $rows+1$ | | for (j = 0; j < cols; j++) | 1 | $rows \cdot (cols+1)$ | | | | 1 | | | | | | | |

The total steps are $2 \cdot rows \cdot cols + 2 \cdot rows + 1$ . If we assume rows and cols are roughly equal to $N$ , the dominant term is . Thus, the time complexity is .

4. Asymptotic Notations

Asymptotic notations are mathematical tools used to describe the limiting behavior of an algorithm's running time or space requirements as the input size approaches infinity. They allow us to classify algorithms into categories based on their growth rate, ignoring constant factors and lower-order terms that become insignificant for large inputs.

4.1. Big O Notation ( $O$ )

Big O Notation describes the upper bound or worst-case running time of an algorithm. It tells us the longest amount of time an algorithm could possibly take to complete.

Definition: A function $f(n)$ is $O(g(n))$ (read as "f of n is big oh of g of n") if and only if there exist positive constants $C$ and $n_0$ such that: $f (n) \leq$ Where and .

Purpose:

To express the upper bound of the running time of an algorithm.
To specify worst-case time complexity.

Examples:

$3n + 2 = O(n)$ because $3n + 2 \le 4n$ for $n \ge 2$ (here ).

4.2. Omega Notation ( $\Omega$ )

Omega Notation describes the lower bound or best-case running time of an algorithm. It tells us the minimum amount of time an algorithm takes to complete.

Definition: A function $f(n)$ is $\Omega(g(n))$ (read as "f of n is omega of g of n") if and only if there exist positive constants $C$ and $n_0$ such that: $f (n) \geq C$ Where and .

Purpose:

To express the lower bound of the running time of an algorithm.
To specify best-case time complexity.

Examples:

$3n + 2 = \Omega(n)$ because $3n + 2 \ge 3n$ for $n \ge 1$ (here $C$ ).

4.3. Theta Notation ( $\Theta$ )

Theta Notation describes the tight bound for an algorithm's performance, meaning its average-case growth rate. It indicates that the algorithm's performance is bounded both from above and below by the same function, up to constant factors.

Definition: A function $f(n)$ is $\Theta(g(n))$ (read as "f of n is theta of g of n") if and only if there exist positive constants $C_1$ , $C_2$ , and such that: Where , , and .

Purpose:

To express both the lower and upper bounds of the running time.
To specify average-case time complexity or a tight bound where best and worst cases are similar.

Example:

$3n + 2 = \Theta(n)$ because $3n \le 3n + 2 \le 4n$ for $n \ge 2$ (here ).

5. Analyzing Recursive Algorithms and Recurrence Relations

Recursive algorithms, which call themselves, often have their time complexity described by recurrence relations. A recurrence relation is an equation or inequality that describes a function in terms of its values on smaller inputs. Solving a recurrence relation means finding a non-recursive function that satisfies it.

5.1. Substitution Method

The substitution method involves making an initial guess for the solution of a recurrence relation and then proving its correctness using mathematical induction.

Example: power(x, n) algorithm

plaintext

Algorithm power(x, n)
{
  if (n == 0)
    return 1;
  else
    return x * power(x, n - 1);
}

The recurrence relation for this algorithm's time complexity, $T(n)$ , would be:

$T(0) = O(1)$ (base case: constant time for comparison and return)
$T(n) = T(n-1) + O(1)$ (recursive case: one recursive call plus constant operations)

Let's assume $T(n) = T(n-1) + c$ . $T(n) = T(n-1) + c$ ...

If $n-k = 0$ , then $k=n$ . $T(n) = T(0) + nc$ Since is a constant, say : This shows is linear, so .

Example: Recursive Fibonacci Series The standard recursive Fibonacci algorithm often has the recurrence: $T(n) = T(n-1) + T(n-2) + c$ (for $n > 1$ )

This recurrence can be approximated as $T(n) \approx 2 \cdot T(n-1)$ , which leads to an exponential solution of $O(2^n)$ .

5.2. Recursion Tree Method

The recursion tree method is a visual technique that converts the recurrence into a tree, where each node represents the cost of a single subproblem. Summing the costs at each level of the tree helps determine the total cost. This method is excellent for generating educated guesses for the substitution method.

Example: $T(n) = T(n/4) + T(n/2) + n^2$

Let's visualize the costs at each level:

text

                               n^2       (Cost at root)
                              /   \
                             /     \
                            /       \
                           /         \
                 T(n/4)           T(n/2)
                (n/4)^2           (n/2)^2    (Cost at level 1: (n/4)^2 + (n/2)^2 = n^2/16 + n^2/4 = 5n^2/16)
               /  \             /  \
              /    \           /    \
     T(n/16) T(n/8)  T(n/8) T(n/4)
     (n/16)^2 (n/8)^2 (n/8)^2 (n/4)^2  (Cost at level 2: (n/16)^2 + (n/8)^2 + (n/8)^2 + (n/4)^2 = (1+2+2+4)n^2/256 = 9n^2/256)
     ...                                  ...

The sum of costs at each level forms a geometric series: Level 0: $n^2$ Level 1: $(n/4)^2 + (n/2)^2 = n^2/16 + n^2/4 = (5/16)n^2$ Level 2: ...

The total cost is the sum of costs at all levels. $T(n) = n^2 + (5/16)n^2 + (9/256)n^2 + \dots$

Notice that the first term $n^2$ is the largest. Since the sum of a geometric series where the common ratio is less than 1 converges to a constant times the first term, the total sum will be dominated by the initial term. In this case, $(5/16) < 1$ . Thus, the total time complexity is $\Theta(n^2)$ .

6. C++ Code Example: Sum Array

Here's a C++ implementation of the array sum algorithm, demonstrating its $O(n)$ time complexity and $O(n)$ space complexity.

cpp

#include <iostream> // Required for input/output operations
#include <vector>   // Required for using std::vector
 
// Function to calculate the sum of elements in an array (vector)
// Time Complexity: O(n) - where n is the number of elements in the vector
// Space Complexity: O(n) - for storing the input vector 'arr'
//                   O(1) - if considering only auxiliary space (excluding input)
double sumArrayElements(const std::vector<double>& arr) {
    // 1. Initialize sum variable
    // This operation takes constant time (O(1)) and constant space (O(1)).
    double totalSum = 0.0; 
 
    // 2. Iterate through each element of the array
    // The loop runs 'n' times, where 'n' is the size of the vector.
    // Each iteration involves:
    //    - comparison (i < arr.size())
    //    - addition (totalSum += arr[i])
    //    - increment (i++)
    // These are all constant time operations.
    // Therefore, the loop's contribution to time complexity is O(n).
    for (size_t

Explanation of C++ Example Complexity:

Time Complexity: The dominant part is the for loop, which iterates arr.size() (let's say $n$ ) times. Inside the loop, operations are constant time. Hence, the total time complexity is $O(n)$ .
Space Complexity:
- Input Space: The std::vector<double>& arr takes $O(n)$ space to store the input elements. If we consider this part of the algorithm's space, it's $O(n)$ .

Summary

Performance analysis evaluates an algorithm's resource usage (time and memory).
Space complexity measures the memory an algorithm needs, comprising a fixed part ( $C$ ) for code/variables and a variable part ( $S_P(instance)$ ) dependent on input size.
Time complexity measures the execution time, focusing on run-time, not compile time. It is determined by counting basic operations or using frequency tables.
Asymptotic notations ( $O$ , $\Omega$ , ) classify algorithms by their growth rate for large inputs, abstracting away machine specifics.

Assessed progress

Performance Analysis: Space and Time Complexity

Performance Analysis: Space and Time Complexity

1. What is Performance Analysis?

2. Space Complexity

3. Time Complexity

4. Asymptotic Notations

4.1. Big O Notation ( $O$ )

4.2. Omega Notation ( $\Omega$ )

4.3. Theta Notation ( $\Theta$ )

5. Analyzing Recursive Algorithms and Recurrence Relations

5.1. Substitution Method

5.2. Recursion Tree Method

6. C++ Code Example: Sum Array

Summary

Key Concepts

Performance Analysis

Space Complexity

Time Complexity

Big O Notation ($O$)

Asymptotic Notations

Quick Check

Advanced Data Structures

Advanced Data Structures