How to calculate space complexity of different algorithms(recursive, divide and conquer, greedy, etc.)(with examples)

1. Recursive Algorithms:

- List the data structures and variables utilized in each recursive call.

- Calculate the amount of memory each recursive call will use, taking into account function call overhead and any additional memory allocations.

- Based on the quantity of recursive calls and their space requirements, write the recurrence relation for the space complexity.

Example: Fibonacci series recursively.

Code:

int fibonacci(int n) {

if (n <= 1) {

return n;

} else {

return fibonacci(n - 1) + fibonacci(n - 2);

}

}

In this case, the space complexity is determined by the maximum depth of the recursion. Each recursive call requires space for function call overhead and local variables. The space required for each call is constant. Therefore, the space complexity of this Fibonacci algorithm is O(n).

2. Divide and Conquer Algorithms:

- List the variables and data structures that were applied to each subproblem.

- Calculate the amount of storage needed for each subproblem, taking into account any auxiliary arrays or data structures.

- Based on the quantity of subproblems and their spatial demands, construct the recurrence relation for the space complexity.

Example: Merge Sort.

Code:

void merge(int arr[], int low, int mid, int high) {

// Merge two sorted subarrays

}

void mergeSort(int arr[], int low, int high) {

if (low < high) {

int mid = (low + high) / 2;

mergeSort(arr, low, mid);

mergeSort(arr, mid + 1, high);

merge(arr, low, mid, high);

}

}

The space complexity of Merge Sort can be calculated by analyzing the space required for each recursive call and any auxiliary data structures used. In this case, the space required for each call is constant, and the algorithm does not require additional space proportional to the input size. Therefore, the space complexity of Merge Sort is O(n), linear space.

3. Greedy Algorithms:

- List the data structures and variables that the algorithm uses.

- Calculate the amount of space needed for any additional data structures the algorithm uses.

- Consider the size of the input and the precise operations that the algorithm performs to determine the space needs.

Example: Activity Selection Problem.

Code:

struct Activity {

int start;

int finish;

};

int activitySelection(Activity arr[], int n) {

sort(arr, arr + n, [](Activity a, Activity b) {

return a.finish < b.finish;

});

int count = 1;

int prevFinish = arr[0].finish;

for (int i = 1; i < n; i++) {

if (arr[i].start >= prevFinish) {

count++;

prevFinish = arr[i].finish;

}

}

return count;

}

The space complexity of the Greedy Activity Selection algorithm depends on the space required for the array of activities arr and any auxiliary variables used. In this case, the space required is proportional to the input size n for the array of activities. Therefore, the space complexity of this algorithm is O(n), linear space.