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 will be arranged for you after you learn the core frameworks of several common algorithms. By that time, your knowledge base will be sufficient to easily understand the various scenarios of time and space complexity analysis.
Since the content later in this chapter will guide you through implementing common sorting algorithms and data structures, I will analyze their time complexity. Therefore, it is necessary to introduce the concept of time/space complexity and the simplified methods for analyzing them in advance to avoid confusion for beginners.
For beginners, you only need to remember the following points:
Time and space complexity are expressed using Big O notation (such as , etc.). These are estimates, not precise calculations.
Time complexity measures an algorithm's execution efficiency, while space complexity measures its memory consumption. Both are better when they are smaller.
For example, an algorithm with time complexity is more efficient than one with , and an algorithm with space complexity consumes less memory than one with .
Of course, we generally need to explain what this n
represents, such as the length of the input array.
- How to estimate? For now, you can simply understand: time complexity is determined by the number of nested for loops; space complexity is determined by how much space the algorithm allocates to store data.
Note
The method I mentioned here of estimating time complexity by the number of nested for loops is merely a simplification and is not accurate. The correct methods will be introduced in the Practical Guide to Algorithm Time and Space Complexity Analysis. However, for beginners learning the content of this chapter, this estimation method is sufficient.
Let me give a few examples for a clearer understanding.
Example One, Time Complexity , Space Complexity :
// 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 , 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 .
Example 2, Time Complexity , Space Complexity :
// 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 , where n
represents the length of the nums
array.
Our algorithm only uses two variables, i
and j
, which results in a constant level of space consumption, so the space complexity is .
You might argue that the inner for loop does not iterate over the entire array and might return early, suggesting the actual execution count should be less than n^2
. Is the time complexity still ?
Yes, it remains . As mentioned earlier, Big O notation is an estimate and does not require precise calculation. For different inputs, the algorithm's actual execution count may indeed be less than n^2
, but we do not need to be concerned with that.
We only need to know that when we see nested for loops, the time complexity is .
Example Three, Time Complexity , Space Complexity :
// 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;
}
The algorithm contains only one for loop, so the time complexity is , where n
represents the length of the nums
array.
We declared a new array res
, which is the same length as the nums
array, so the space complexity is .
For beginners, understanding the basic time and space complexity analysis mentioned above is sufficient for now. Let's continue learning.