Skip to main content
Practice

Review of Algorithm Complexity Concepts

Algorithm complexity is a measure of how efficient an algorithm is. In this session, we will review the Big O notation, and the concepts of time complexity and space complexity that we covered previously.


Big O Notation​

Big O notation is a mathematical representation used to describe the time complexity or space complexity of an algorithm.

This notation expresses how the resources (time or space) required by an algorithm change as the input size increases.


Examples of Big O Notation​

  • O(1) Constant Time: Takes a constant time regardless of input size.

  • O(n) Linear Time: The execution time increases linearly with the input size.

  • O(n^2) Quadratic Time: Doubling the input size quadruples the execution time. Nested loops fall into this category.


Time Complexity​

Time complexity is a measure of how the time required to solve a problem by an algorithm changes with the size of the input. It is commonly used to predict how many operations an algorithm needs in the worst-case scenario.

For example, in the code below, if the input size is 5, it requires 5 operations. If the input size is 10, it requires 10 operations.

Example of O(n) Time Complexity
def example_function(n):
    for i in range(n):
        print(i)

# Function call
example_function(5)

Therefore, the time complexity of the simple loop above increases proportionally with the input size (n), making it O(n).


Space Complexity​

Space complexity is a measure of the amount of memory space used by an algorithm during its execution.

For example, the function below uses a fixed-size array regardless of the input size (n), so the space complexity is O(1).

Example of O(1) Space Complexity
def example_function():
    fixed_array = [1, 2, 3, 4, 5] # Occupies a fixed-size array
    print(fixed_array)

# Function call
example_function()