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 is a mathematical representation used to describe the time complexity or space complexity of an algorithm.

This notation expresses how an algorithm's resource usage (time or space) grows relative to the input size.

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

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

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

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.

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

Copy
def example_function():
    fixed_array = [1, 2, 3, 4, 5] # Occupies a fixed-size array
    print(fixed_array)

# Function call
example_function()