Time Complexity and Space Complexity

Analyzing the efficiency of an algorithm in terms of how much time and space (memory) they require as the input size grows.

1. Time Complexity

Time complexity refers to the amount of time an algorithm takes to complete as a function of the size of the input data. It's typically expressed using Big O notation, which describes the upper bound of the time required in the worst-case scenario.

• O(1): Constant time – The algorithm takes the same amount of time regardless of the input size.
• O(log n): Logarithmic time – The time grows logarithmically with the input size.
• O(n): Linear time – The time grows linearly with the input size.
• O(n log n): Log-linear time – Common in algorithms like mergesort or heapsort.
• O(n^2): Quadratic time – The time grows proportionally to the square of the input size, common in simple sorting algorithms like bubble sort.
• O(2^n): Exponential time – The time doubles with each additional element in the input, typical of certain recursive algorithms.
• O(n!): Factorial time – Extremely slow, common in problems involving permutations.

2. Space Complexity

Space complexity refers to the amount of memory an algorithm uses as a function of the input size. It also uses Big O notation to describe the upper bound of the memory required.

• O(1): Constant space – The algorithm uses a fixed amount of memory regardless of the input size.
• O(n): Linear space – The memory required grows linearly with the input size.
• O(log n): Logarithmic space – Memory usage grows logarithmically with the input size.
• O(n^2): Quadratic space – Memory usage grows proportionally to the square of the input size.

Example

Consider a simple loop that sums up an array of numbers:

def sum_array(arr):
    total = 0            # O(1) space
    for num in arr:      # O(n) time
        total += num     # O(1) time
    return total        

• Time complexity: O(n) because the algorithm iterates through each element of the array once.
• Space complexity: O(1) because the algorithm uses a constant amount of extra space (the variable total) regardless of the input size.