Skip to main content
Practice

Time and Space Complexity of Algorithms

In this lesson, we will explore algorithm complexity through simple Python examples to make the concepts easier to understand.

We will learn to evaluate an algorithm's efficiency by considering time complexity and space complexity.


Time Complexity​

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


Linear Time Complexity O(n) Example​

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.

Linear Time Complexity Example
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).


Quadratic Time Complexity O(n²) Example​

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

The example below prints pairs of combinations using nested loops.

Quadratic Time Complexity Example
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​

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


Constant Space Complexity O(1) Example​

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.

Constant Space Complexity Example
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).


Linear Space Complexity O(n) Example​

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

Below is an example demonstrating list cloning.

Linear Space Complexity Example
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).

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.