We all know that data structures and algorithms address the concepts of speed and efficiency—how to make code run faster and use storage space more efficiently. Therefore, the execution efficiency of algorithms is a crucial consideration. How do we measure the efficiency of the algorithmic code we write? This brings us to today’s topic: analyzing time and space complexity.

Why is complexity analysis needed?

You might be wondering why I need to analyze time and space complexity when I can simply run the code once and gather statistics and monitoring data on algorithm execution time and memory usage. Can’t this real-time data provide a more accurate assessment? While evaluating algorithm efficiency through actual runs is valid, this approach is often referred to in data structure and algorithm books as post hoc analysis. However, it does come with significant limitations.

  1. The test results heavily rely on the testing environment.

Test results can vary significantly depending on the test environment, particularly due to differences in hardware. For instance, running the same piece of code on an Intel Core i9 processor versus an Intel Core i3 processor will naturally result in faster execution on the i9. Similarly, if code ‘A’ runs faster than code ‘B’ on this machine initially, switching to another machine could yield completely opposite results.

  1. The test results are greatly influenced by the size of the data.

Consider a sorting algorithm as an example: the order of the data significantly affects the execution time of the sorting process. In cases where the data is already sorted, the algorithm requires minimal operations, resulting in very short execution times. Furthermore, when the test data size is too small, the algorithm’s performance may not accurately reflect its capabilities. For instance, with small datasets, insertion sort could potentially outperform quicksort.

Therefore, we need a method to roughly estimate the execution efficiency of an algorithm without relying on specific test data. Complexity analysis is fundamental to efficient algorithm design and implementation in software development. It plays a crucial role in evaluating and predicting the performance characteristics of algorithms and data structures. By thoroughly understanding complexity, developers can make informed decisions to optimize both time and space efficiency in their code.

In the domain of algorithms:

  • Time Complexity: This metric assesses how an algorithm’s execution time scales with the size of its input. Algorithms with lower time complexity generally perform better on larger datasets, crucial for applications requiring fast processing speeds or handling extensive computations.
  • Space Complexity: This dimension measures the amount of memory an algorithm requires relative to its input size. Algorithms with lower space complexity are advantageous in memory-constrained environments, such as mobile devices or embedded systems.

Big O notation

The execution efficiency of an algorithm can be understood as the time it takes for the algorithm’s code to run. However, how can one estimate the execution time of a piece of code without actually running it?

Let’s consider a straightforward example: a simple piece of code that calculates the sum of integers from 1 to n. I will guide you through the process of estimating the execution time of this code.

1
2
3
4
5
6
7
8
int sum(int n) {
    int s = 0;
    int i = 1;
    for (; i <= n; ++i) {
        s = s + i;
    }
    return s;
}

From the perspective of the CPU, each line of this code performs a similar sequence of operations: reading data, performing arithmetic, and writing data. While the number of CPU executions and the time taken for each line vary, for the sake of estimation, we assume each line takes the same amount of time, referred to as unit_time. Based on this assumption, what is the total execution time of this code?

The 2nd and 3rd lines each require 1 unit_time of execution time, while the 4th and 5th lines iterate$n$times, requiring $( 2n \cdot \text{unit_time} )$ of execution time. Therefore, the total execution time of this code is $( (2n+2) \cdot \text{unit_time} )$. It can be seen that the execution time$T(n)$of all code is directly proportional to the number of executions per line.

Continuing with this analytical approach, let’s now reconsider another piece of code.

1
2
3
4
5
6
7
8
9
10
11
int sum(int n) {
    int s = 0;
    int i = 1;
    int j = 1;
    for (; i <= n; ++i) {
        j = 1;
        for (; j <= n; ++j) {
            s = s +  i * j;
        }
    }
}

We still assume each statement takes unit_time to execute. Now, what is the total execution time$\ T(n) $for this code?

The 2nd, 3rd, and 4th lines each require 1 unit_time. The 5th and 6th lines iterate$n$times, requiring $( 2n \cdot \text{unit_time} )$. The 7th and 8th lines iterate$n^2$times, thus requiring $( 2n^2 \cdot \text{unit_time} )$. Therefore, the total execution time$T(n)$for the entire code segment is $( (2n^2 + 2n + 3) \cdot \text{unit_time} )$.

While the exact value of unit_time remains unknown, analyzing the execution times of these code segments reveals a crucial rule: the total execution time$T(n)$correlates directly with the number of executions$f(n)$of each line of code.

This observation can be encapsulated into a formula, setting the stage for the introduction of Big O notation!

$T(n)=O(f(n))$

Here,$T(n)$represents the time complexity of code execution, where$n$denotes the size of the input data, and$f(n)$signifies the total number of times each line of code is executed. In Big O notation, denoted by O,$T(n)$is proportional to$f(n)$.

For instance,$T(n) = O(2n+2)$in the first example, and$T(n) = O(2n^2+2n+3)$in the second. Big O notation expresses the growth rate of execution time as data size increases, known as asymptotic time complexity.

In practical terms, this notation doesn’t precisely indicate actual execution time but rather how it scales with input size, such as when$n$is large, say 1,000,000 or 10,000,000. In the formula, lower-order terms, constants, and coefficients do not affect the growth trend and can be ignored, focusing only on the dominant term.

Therefore, for the two code segments mentioned earlier, their time complexity in Big O notation would be:$T(n) = O(n)$and$T(n) = O(n^2)$.

Conclusion

In conclusion, complexity analysis is not merely an academic exercise but a fundamental practice that underpins effective software engineering. By leveraging insights into time and space complexities, developers empower themselves to craft solutions that meet performance expectations, enhance user experience, and optimize resource consumption. Embracing complexity analysis is essential for anyone striving to build reliable, efficient software systems in today’s dynamic technological landscape.