Basic Time Complexity

Considering this is the first chapter, I will not provide an exhaustive explanation of time and space complexity. The detailed Practical Guide to Algorithm Time and Space Complexity Analysis is scheduled after you have learned the core frameworks of several common algorithms. By then, your knowledge base will be sufficient to easily understand the various scenarios of time and space complexity analysis.

Since later in this chapter, we will implement common sorting algorithms and data structures, I will analyze their time complexity. Thus, it is necessary to introduce the concept of time/space complexity in advance, along with 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 represented using Big O notation (such as $O(1), O(n^2), O(logn)$, etc.). These are estimates, not precise calculations, and only the term with the highest growth rate 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. Time complexity measures the execution efficiency of an algorithm, while space complexity measures its memory consumption. Both are more desirable when lower.

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 n represents, such as the length of the input array.

3. How to estimate? For now, you can simply understand that: time complexity is related to the nesting levels of for loops; space complexity relates to how much space the algorithm allocates to store data.

Let's look at a few examples for a more intuitive understanding.

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;
}

The algorithm includes a for loop that iterates through the nums array, so the time complexity is $O(n)$, where n represents the length of the nums array.

Our algorithm only uses a sum variable. Since nums is provided as input in the problem, it is not counted in the space complexity of our algorithm, making the space complexity $O(1)$.

Example 2, Time Complexity $O(n^2)$, Space Complexity $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 includes 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 two variables, i and j, which is a constant level of space consumption, so the space complexity is $O(1)$.

You might argue that the inner for loop does not traverse the entire array and may return early, meaning the actual execution times of the algorithm might be less than n^2. Does this mean the time complexity is still $O(n^2)$?

Yes, it is still $O(n^2)$. As mentioned, Big O notation is an estimate and does not require precise calculation. 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 that.

We just need to recognize that when we see nested for loops, the time complexity is $O(n^2)$.

Example Three, 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)$. It is important to note that allocating space for an array and initializing it also requires time, so the time complexity is also $O(n)$.

Example Four, 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.