Space Complexity Analysis

Definition

Space complexity measures the approximate space requirement of an algorithm to execute in memory.

Formula:

Total Space = Input Space + Auxiliary Space

• Input Space: Space required to store input data
• Auxiliary Space: Extra space required to process the algorithm

Example: Linear Search

int linearSearch(int arr[], int key) {
    // Input variables: arr, key, size
    // Processing variables: i (loop counter)

    for(int i = 0; i < arr.length; i++) {
        if(key == arr[i])
            return i;
    }
    return -1;
}

Space Analysis:

• Auxiliary space is constant (only loop variable i)
• S(n) = O(1) - Constant space complexity

Algorithm Analysis: Iterative vs Recursive

Iterative Approach

• Uses loops for repetition
• Generally more space-efficient

Example: Factorial (Iterative)

int fact(int num) {
    int f = 1;
    for(int i = 1; i <= num; i++) {
        f *= i;
    }
    return f;
}

Complexity Analysis: