Time and Space Complexity of Algorithms

In this lesson, we will delve into the complexity of algorithms using simple Python code examples to make the concepts easily understandable.

We will learn how to evaluate how efficient an algorithm is by considering time complexity and space complexity.

Time Complexity measures how the time required by an algorithm to solve a problem varies with the size of the input.

Algorithms with linear time complexity have execution time that increases in direct proportion to the size of the input.

Below is a simple example code that prints each element in a list.

Copy
numbers = [1, 2, 3, 4, 5]

for number in numbers:
    print(number)

As the size of the list increases, the number of iterations in the for loop increases accordingly.

Therefore, this code has a time complexity proportional to the input size n, i.e., O(n).

Algorithms with quadratic time complexity have execution time that increases in proportion to the square of the input size.

Below is an example that prints pairs of combinations using nested loops.

Copy
numbers = [1, 2, 3, 4, 5]

for i in numbers:
    for j in numbers:
        print(f"({i}, {j})")

In the code above, the first for loop executes n times, and for each iteration, the second for loop also executes n times.

Therefore, the total execution is n * n = n² times, resulting in time complexity proportional to the square of the input size n, i.e., O(n²).

Space Complexity measures the amount of memory space an algorithm uses during execution.

Algorithms with constant space complexity use a fixed amount of memory independent of the input size.

For instance, the following code simply calculates the square of a number.

Copy
def square(number):
    return number * number

result = square(5)

print(result)

This function uses minimal memory to store the argument number and the result.

Since the memory requirement is constant regardless of the input size, the space complexity is O(1).

Algorithms with linear space complexity use memory that increases in proportion to the size of the input.

Below is an example demonstrating list cloning.

Copy
def clone_list(original_list):
    new_list = original_list[:]  # Copy the entire list
    return new_list

original = [1, 2, 3, 4, 5]
cloned = clone_list(original)

print(cloned)

The clone_list function uses memory proportional to the length of original_list to create a new list.

If the input list has a size n, the cloned list occupies the same memory space as n.

Thus, the space complexity of this function is O(n).