Basic Time Complexity

Since this is the first chapter, I will not cover every detail of time and space complexity. A more thorough Practical Guide to Algorithm Time and Space Complexity Analysis is arranged for after you have learned the core framework of several common algorithms. By then, you will have enough knowledge to easily understand various scenarios of complexity analysis.

Because later in this chapter you will implement common sorting algorithms and data structures, I will analyze their time complexity. So, I want to introduce the concepts of time/space complexity, as well as some simplified methods for analyzing them, to avoid confusion for beginners.

For beginners, you only need to keep the following points in mind:

1. Time and space complexity are represented by Big O notation (such as $O(1), O(n^2), O(logn)$, etc). These are estimates, not exact calculations. You can ignore constants and lower-order terms, and only keep the highest-order term.

For example, $O(2n^2 + 3n + 1)$ is the same as $O(n^2)$, and $O(1000n + 1000)$ is the same as $O(n)$.

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

3. Time complexity measures the execution efficiency of an algorithm, and space complexity measures its memory usage. The smaller, the better for both.

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

Of course, we usually specify what $n$ stands for, such as the length of the input array.

4. How to estimate? For now, you can simply understand: in most cases, time complexity depends on the highest number of nested for loops; space complexity depends on how much extra space the algorithm uses to store data.

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

Time and Space Complexity Case Analysis

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

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

# input an integer array, return the sum of all elements
def getSum(nums: List[int]) -> int:
    sum = 0
    for i in range(len(nums)):
        sum += nums[i]
    return sum

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

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

The algorithm contains a for loop that traverses the nums array, so the time complexity is $O(n)$, where n is the length of the nums array.

Our algorithm only uses one variable sum. The nums array is given as input and does not count toward the algorithm's space complexity, so the space complexity is $O(1)$.

Example 2: Time Complexity $O(n)$, Space Complexity $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;
}

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

# Calculate the sum when n is a multiple of 10, otherwise return -1
def sum(n: int) -> int:
    if n % 10 != 0:
        return -1
    sum = 0
    for i in range(n + 1):
        sum += i
    return sum

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

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

In fact, the algorithm only performs the for loop when n is a multiple of 10, so the time complexity is $O(n)$ in that case. In other cases, the algorithm returns directly, and the time complexity is $O(1)$.

However, when analyzing algorithm complexity, we consider the worst case. So, the time complexity of this algorithm is $O(n)$, and the space complexity is $O(1)$.

Example 3: 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;
}

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

# Does the array contain two numbers whose sum is target?
def hasTargetSum(nums: List[int], target: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

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

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

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

The algorithm only uses two variables i and j, which is a constant amount of space. Therefore, the space complexity is $O(1)$.

You might think that the inner for loop does not always traverse the entire array, and may return early, so the actual number of executions is less than $n^2$. Is the time complexity still $O(n^2)$?

Yes, it is still $O(n^2)$. For different inputs, the actual number of executions may be less than $n^2$, but we only need to consider the worst-case time complexity.

Each for loop has a worst-case time complexity of $O(n)$. Nesting them together results in a total time complexity of $O(n^2)$.

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

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

void exampleFn(int n) {
    vector<int> nums(n);
}

def exampleFn(n: int):
    nums = [0] * n

func exampleFn(n int) {
    nums := make([]int, n)
}

function exampleFn(n) {
    let nums = new Array(n);
}

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

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

Time complexity is not only determined by visible for loops. Every line of code may hide some time complexity. This is why understanding the underlying implementation of common data structures in your programming language is key to accurately analyzing time complexity.

Example 5: 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;
}

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

# input an integer array, return a new array where each element
# is the square of the corresponding element in the original array
def squareArray(nums: List[int]) -> List[int]:
    res = [0] * len(nums)
    for i in range(len(nums)):
        res[i] = nums[i] * nums[i]
    return res

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

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

Initializing the res array takes $O(n)$ time, and there is a for loop with $O(n)$ time complexity, so the total time complexity is still $O(n)$, where n is the length of the nums array.

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

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