1. Best Case Space Complexity:

- The smallest amount of space needed by an algorithm to operate on a particular input is referred to as the best case space complexity.

- It is based on the supposition that the input is in the best possible shape or condition for the algorithm, causing the algorithm to use the least amount of memory.

- Best case analysis aids in identifying situations when the algorithm uses the least amount of storage.

2. Average Case Space Complexity:

- The average case space complexity takes into account how much space an algorithm is likely to consume when given inputs that are randomly or evenly distributed.

- It reflects the algorithm's average space consumption across a range of potential inputs, accounting for the possibility or probability that each input will occur.

- Understanding the typical space requirements of the algorithm in practical situations is aided by average case analysis.

3. Worst Case Space Complexity:

- Worst scenario is the maximum amount of space needed for an algorithm to operate on a given input.

- It makes the most memory-intensive assumption that the input is in the poorest possible shape or condition for the program.

- Worst case analysis aids in identifying situations in which the algorithm uses the most storage and serves as an upper limit for memory needs.

Examples of simple codes and their space complexity calculations

1. Linear Search:

Code:

int linearSearch(int arr[], int n, int target) {

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

if (arr[i] == target) {

return i;

}

}

return -1;

}

Space Complexity: O(1)

The code performs a linear search through the array arr of size n. It does not require any additional data structures or memory allocations, resulting in constant space complexity.

2. Bubble Sort:

Code:

void bubbleSort(int arr[], int n) {

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

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

if (arr[j] > arr[j+1]) {

int temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

}

Space Complexity: O(1)

The code implements the Bubble Sort algorithm to sort the array arr of size n. It performs in-place swapping of elements and does not require any additional memory, resulting in constant space complexity.

3. Fibonacci Series:

Code:

int fibonacci(int n) {

if (n <= 1) {

return n;

} else {

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

}

}

Space Complexity: O(n)

The code calculates the Fibonacci series recursively. Each recursive call adds a new stack frame to the call stack, which consumes memory. The maximum depth of the call stack is n, resulting in linear space complexity.

4. 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);

}

}

Space Complexity: O(n)

The code implements the Merge Sort algorithm, which uses a recursive divide-and-conquer approach. It creates temporary arrays during the merging step but does not require additional space proportional to the input size n. The space complexity remains linear.