Basic Time Complexity

Considering that 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 arranged after you have learned the core frameworks of several common algorithms. By then, your knowledge base will allow you to easily understand various scenarios of time and space 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. Therefore, it is necessary to introduce the concepts of time/space complexity and the simplified methods for analyzing them to avoid confusion for beginners.

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

1. Time and space complexity are expressed using Big O notation (such as $O(1), O(n^2), O(logn)$, etc.). These are estimates and do not require precise calculations, retaining only the highest order terms.

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 analyze the worst-case complexity.

3. Time complexity measures the execution efficiency of an algorithm, and space complexity measures the memory consumption of an algorithm, both of which 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)$ consumes less memory than one with $O(n)$.

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

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

Here are a few examples for a more intuitive understanding.

Case Studies on Time/Space Complexity

Example 1, 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 has a nested two-layer for loop, 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 number of executions of the algorithm should be less than $n^2$. Is the time complexity still $O(n^2)$?

Yes, it is still $O(n^2)$. As mentioned before, Big O notation is an estimation and does not require exact calculation. For different inputs, the actual execution count of the algorithm will indeed be less than $n^2$, but we don't need to be concerned with that.

Simply put: when you see nested for loops, the 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)$.

Allocating array space and initializing the array also takes time, so the time complexity is $O(n)$ as well.

Time complexity is not only represented by the visible for loops; every line of code may have hidden time complexity. Therefore, understanding the implementation principles of common data structures is the foundation 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.