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 for after you've 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 this chapter will guide you through implementing common sorting algorithms and data structures, I will analyze their time complexities. Therefore, it is essential to introduce the concepts of time/space complexity and the simplified methods of analysis in advance 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 (like $O(1), O(n^2), O(logn)$, etc.). These are estimates, not precise calculations, and only the highest growth term is retained.

   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 the complexity of an algorithm, we generally consider the worst-case complexity.

3. Time complexity measures an algorithm's execution efficiency, while space complexity measures its memory consumption. The lower they are, the better.

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

   Of course, we generally need to specify what this n represents, such as the length of the input array.

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

Let's look at a few examples for clearer understanding.

Time/Space Complexity Case Analysis

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 contains two nested for loops, so the time complexity is $O(n^2)$, where n represents the length of the nums array.

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

You might say that the inner for loop doesn't iterate through the entire array and may return early, so the actual execution count 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 estimate and does not require exact calculations. For different inputs, the actual execution count of the algorithm may indeed be less than $n^2$, but we don't need to worry about 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 space for the array and initializing it also takes time, so the time complexity is $O(n)$ as well.

Time complexity is not only reflected in visible for loops; every line of code can have hidden time complexity. Therefore, understanding the implementation principles of common data structures is fundamental to 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.