[Data Structure] Topic 1: Time and Space Complexity

Authored by Tony Feng

Created on March 17th, 2022

Last Modified on March 18th, 2022

Time Complexity

Def

The efficiency of the algorithm
The relationship between the algorithm’s input and its execution time

Common Cases

O(1)

1
2
3
4


def O1(num):
    i = num
    j = num * 2
    return i + j

O(n)

1
2
3
4
5


def ON(num):
    total = 0
    for i in range(0, num):
        total += i
    return total

O(m+n)

1
2
3
4
5
6
7


def OMN(num1, num2):
    total = 0
    for i in range(0, num1):
        total += 1
    for j in range(0, num2):
        total += 1
    return total

O(log(n))

1
2
3
4
5


def OlogN(num):
    i = 1
    while i < num:
        i = i * 2
    return i

O(n*log(n))

1
2
3
4
5
6
7
8


def ONlogN(num1, num2):
    total = 0
    tmp = 1
    for i in range(0, num1):
        while tmp < num2:
            total = i + tmp
            tmp = tmp * 2
    return total

O(n²)

1
2
3
4
5
6


def ON2(num):
    total = 0
    for i in range(0, num):
        for j in range(0, num):
            total += 1
    return total

Comparison

O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n²) < O(2ⁿ) < O(n!)

Space Complexity

Def

The relationship between the algorithm’s input and its memory space needed

Common Cases

O(1)

1
2
3
4
5
6


# total is a int variable with a 4-bytes memory
def O1(num):
    total = 0
    for i in range(0, num):
        total += i
    return total

O(n)

1
2
3
4
5
6


# nodes is a list whose memory depends on the input
def On(nums):
    nodes = []
    for num in nums:
        nodes.append(num)
    return nodes

Analysis Approches

Check the variable
If the variable varies in response to the input, e.g. array, linked list, hash map, etc., the space complexity may be O(n), O(n²) …
If not, it is O(1)
Determine the space complexity case-by-case.
Be careful with the recursion. Info in each level are stored on a recursive stack.

Summary

There is a trade-off between time and space.
Time should be considered in the first place.

Time Complexity

Def

Common Cases

Comparison

Space Complexity

Def

Common Cases

Analysis Approches

Summary

Reference