Software Engineering basics - Time Complexity and Space Complexity

Time Complexity and Space Complexity are two essential concepts in computer science used to analyze how efficient an algorithm is in terms of:

  • Time Complexity – How the runtime of an algorithm increases as the size of the input increases.

  • Space Complexity – How much additional memory (space) an algorithm uses as the input size increases.

1. Time Complexity

Time complexity estimates how fast an algorithm runs relative to input size n.

Common Time Complexities:

Notation Name Example
O(1) Constant Time Accessing an array element by index
O(log n) Logarithmic Time Binary search
O(n) Linear Time Looping through an array
O(n log n) Linearithmic Time Merge sort, Quick sort (average case)
O(n²) Quadratic Time Nested loops (e.g., Bubble sort)
O(2ⁿ) Exponential Time Solving the Traveling Salesman problem (brute-force)
O(n!) Factorial Time Generating all permutations

2. Space Complexity

Space complexity measures the total memory used by an algorithm, including:

  • Input storage

  • Auxiliary space (temporary variables, stacks, recursion calls)

Common Space Complexities:

Notation Example
O(1) In-place sorting like Bubble Sort
O(n) Storing a separate array or list
O(log n) Recursive binary search
O(n²) 2D matrix storage or memoization table

3. Why Are These Important?

  • Help choose the best algorithm for a problem.

  • Crucial in systems with performance or memory constraints.

  • Allow comparison between solutions for scalability.

Quick Examples

Example 1: Linear Search

def linear_search(arr, x):
    for item in arr:
        if item == x:
            return True
    return False

  • Time Complexity: O(n)

  • Space Complexity: O(1)

Example 2: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

  • Time Complexity: O(n log n)

  • Space Complexity: O(n)