Examples for Calculation of Time and Space complexity

Let’s illustrate time and space complexity with some examples in Python. We’ll cover constant time, linear time, and quadratic time complexities. These examples will help you understand how to calculate the complexity of a program.

1. Constant Time Complexity – O(1)

An algorithm with O(1) complexity has a fixed execution time regardless of the input size.

def constant_time_example(arr):
    return arr[0]  # Accessing the first element of the array

# Example usage
array = [1, 2, 3, 4, 5]
print(constant_time_example(array))  # Output: 1

2. Linear Time Complexity – O(n)

An algorithm with O(n) complexity has execution time proportional to the input size.

def linear_time_example(arr):
    total = 0
    for num in arr:
        total += num  # Summing all elements of the array
    return total

# Example usage
array = [1, 2, 3, 4, 5]
print(linear_time_example(array))  # Output: 15

3. Quadratic Time Complexity – O(n^2)

An algorithm with O(n^2) complexity has execution time proportional to the square of the input size.

def quadratic_time_example(matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            print(matrix[i][j], end=' ')  # Printing all elements of a 2D matrix
        print()

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
quadratic_time_example(matrix)
# Output:
# 1 2 3 
# 4 5 6 
# 7 8 9

4. Logarithmic Time Complexity – O(log n)

An algorithm with O(log n) complexity has execution time proportional to the logarithm of the input size. A common example is binary search.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example usage
array = [1, 2, 3, 4, 5]
target = 3
print(binary_search(array, target))  # Output: 2

Space Complexity Examples

1. Constant Space Complexity – O(1)

The space used by the algorithm does not grow with the input size.

def constant_space_example(n):
    result = n * (n + 1) // 2  # Sum of first n natural numbers
    return result

# Example usage
n = 5
print(constant_space_example(n))  # Output: 15

2. Linear Space Complexity – O(n)

The space used by the algorithm grows linearly with the input size.

def linear_space_example(n):
    fib_sequence = [0, 1]
    for i in range(2, n):
        fib_sequence.append(fib_sequence[-1] + fib_sequence[-2])
    return fib_sequence

# Example usage
n = 5
print(linear_space_example(n))  # Output: [0, 1, 1, 2, 3]

Conclusion

Understanding the time and space complexity of algorithms is crucial for writing efficient code. By analyzing these examples, you can see how different operations and structures impact the performance of a program. This knowledge will help you make better decisions when designing and implementing algorithms.