Basic Time Complexity

labuladongOriginal

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:

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)$ .

When analyzing algorithm complexity, we look at the worst-case scenario. This will be demonstrated in the examples below.
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.

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.

Note

Some details in the above analysis methods are not rigorous:

Estimating time complexity by counting the number of nested for loops is a simplified method and not completely accurate.
Most of the time we analyze the worst-case complexity, but when measuring the complexity of data structure APIs, we analyze the average complexity.

A more complete analysis method will be introduced in detail in Practical Guide to Algorithm Time and Space Complexity Analysis. The estimation methods above are sufficient for learning the content of this chapter.

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

Time and Space Complexity Example Analysis

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

java

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

cpp

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

python

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

javascript

// 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 uses a for loop to go through the nums array, so the time complexity is $O(n)$ , where n is the length of nums.

We only use a variable sum. The nums array is given as input by the problem, so it does not count towards the space complexity of our algorithm. So the space complexity is $O(1)$ .

Example 2: Time Complexity $O(n)$ , Space Complexity $O(1)$

java

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

cpp

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

python

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

javascript

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

Actually, the for loop only runs if n is a multiple of 10, so the time complexity is $O(n)$ . In other cases, the algorithm returns directly, so the time complexity is $O(1)$ .

But when we analyze algorithm complexity, we only care about the worst case. So the time complexity is $O(n)$ , and the space complexity is $O(1)$ .

Example 3: Time Complexity $O(n^2)$ , Space Complexity $O(1)$

java

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

cpp

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

python

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

javascript

// 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 nums.

We only use two variables i and j. This is a constant amount of extra space, so the space complexity is $O(1)$ .

You might ask: The inner for loop does not always go through the whole array, and it might return early, so isn't the actual time less than $n^2$ ? Is the time complexity really $O(n^2)$ ?

Yes, it is still $O(n^2)$ . In different cases, the actual number of operations might be less than $n^2$ , but we only need to estimate the worst case time complexity.

Each for loop has $O(n)$ time complexity in the worst case, so putting them together gives total time complexity of $O(n^2)$ .

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

java

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

cpp

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

python

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

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

javascript

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

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

The code allocates space for an array and sets $n$ elements to 0. Memory allocation itself can be considered $O(1)$ , but setting each element to 0 is like a hidden for loop (done automatically by the language), so the time complexity is $O(n)$ . The total time complexity is $O(n)$ .

Time complexity is not only about visible for loops. Every line of code could have hidden time costs. So, it is important to understand how common data structures in your programming language work. This helps you analyze time complexity accurately.

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

java

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

cpp

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

python

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

javascript

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

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

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

If you understand the basic complexity analysis above, that is good enough for now. Let's keep learning.