Basic Time Complexity

Considering this is the first chapter, I will not provide an exhaustive explanation of time and space complexity. A detailed Practical Guide to Algorithm Time and Space Complexity Analysis is scheduled after you have learned the core frameworks of several common algorithms, by which time your knowledge reserve will easily accommodate various scenarios of complexity analysis.

Since the later content of this chapter will guide you through implementing common sorting algorithms and data structures, I will analyze their time complexities, so it is necessary to introduce the concept of time/space complexity and the simplified methods for analysis here to prevent confusion for beginners.

For beginners, you only need to remember the following points:

1. Time and space complexities are represented using Big O notation (such as $O(1), O(n^2), O(logn)$, etc.). These are estimates and do not require precise calculations. Constant terms and low-growth terms can be ignored, keeping only the highest growth term.

For example, $O(2n^2 + 3n + 1)$ is equivalent to $O(n^2)$, and $O(1000n + 1000)$ is equivalent to $O(n)$.

2. When analyzing algorithm complexity, we consider the worst-case complexity. This will be demonstrated in the examples below.

3. Time complexity measures the execution efficiency of an algorithm, and space complexity measures its memory consumption. Both are better when smaller.

For example, an algorithm with time complexity $O(n)$ is more efficient than one with $O(n^2)$, and an algorithm with space complexity $O(1)$ uses less memory than one with $O(n)$.

Of course, it is generally necessary to specify what $n$ represents, such as the length of the input array.

4. How to estimate? For now, you can simply understand: time complexity is mostly determined by the maximum nesting level of for loops; space complexity is determined by how much space the algorithm allocates to store data.

Let's illustrate with a few examples for clarity.

Case Studies of Time/Space Complexity

Example One, Time Complexity $O(n)$, Space Complexity $O(1)$:

// input an integer array, return the sum of all elements
int getSum(int[] nums) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    return sum;
}

算法包含一个 for 循环遍历 nums 数组，所以时间复杂度是 $O(n)$，其中 n 代表 nums 数组的长度。

我们的算法只使用了一个 sum 变量，这个 nums 是题目给的输入，不算在我们算法的空间复杂度里面，所以空间复杂度是 $O(1)$。

示例二，时间复杂度 $O(n)$，空间复杂度 $O(1)$：

// Calculate the sum when n is a multiple of 10, otherwise return -1
int sum(int n) {
    if (n % 10 != 0) {
        return -1;
    }
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += i;
    }
    return sum;
}

其实只有当 n 是 10 的倍数时，算法才会执行 for 循环，时间复杂度是 $O(n)$。其他情况下算法会直接返回，时间复杂度是 $O(1)$。

但是算法复杂度只考察最坏情况，所以这个算法的时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。

示例三，时间复杂度 $O(n^2)$，空间复杂度 $O(1)$：

// Does the array contain two numbers whose sum is target?
boolean hasTargetSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return true;
            }
        }
    }
    return false;
}

The algorithm is nested with two for loops, so the time complexity is $O(n^2)$, where $n$ represents the length of the nums array.

Our algorithm only uses two variables, i and j, which is a constant level of space consumption, so the space complexity is $O(1)$.

You might say that the inner for loop does not traverse the entire array and may return early, so the actual execution times of the algorithm should be less than $n^2$. Is the time complexity still $O(n^2)$?

Yes, it is still $O(n^2)$. For different inputs, the actual execution times of the algorithm might indeed be less than $n^2$, but we do not need to focus on these details; estimating the worst-case time complexity is sufficient.

Each for loop has a time complexity of $O(n)$ in the worst case, and when combined, the total time complexity is $O(n^2)$.

Example Four, Time Complexity $O(n)$, Space Complexity $O(n)$:

void exampleFn(int n) {
    int[] nums = new int[n];
}

This function creates an array of size n, so the space complexity is $O(n)$.

In Java, the operation new int[n] allocates array space and initializes all elements to 0. The memory allocation operation itself can be considered $O(1)$ in time complexity, but initializing all elements is equivalent to a hidden for loop, with a time complexity of $O(n)$. Thus, the total time complexity is $O(n)$.

Time complexity is not only reflected in visible for loops; each line of code may have hidden time complexities. Therefore, understanding the implementation principles of common data structures provided by programming languages is the basis for accurately analyzing time complexity.

Example Five, Time Complexity $O(n)$, Space Complexity $O(n)$:

// input an integer array, return a new array where each element is
// the square of the corresponding element in the original array
int[] squareArray(int[] nums) {
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        res[i] = nums[i] * nums[i];
    }
    return res;
}

Initializing the res array in the algorithm requires a time complexity of $O(n)$, which includes a for loop, also having a time complexity of $O(n)$. Therefore, the total time complexity remains $O(n)$, where n represents the length of the nums array.

We declare a new array res with the same length as the nums array, so the space complexity is $O(n)$.

For beginners, understanding these basic analyses of time and space complexity is sufficient for now. Let's continue learning.