Complexities of Space

space

Not only can you use big-O notation to describe the “time complexity” (i.e., running time) of an algorithm, you can also use it to describe the “space complexity” of an algorithm: the amount of space that an algorithm requires based on the size, n, of its input, excluding the input itself.

For instance, whereas linear search might require O(n) time, it might only require O(1) space. Recall Week 3’s pseudocode:

For i from 0 to n-1
    If number behind i'th door
        Return true
Return false

Even though there were n doors, we only needed a constant amount of space, a variable called i, to help us iterate over those doors. The n doors themselves might take up O(n) space, but we exclude size of the algorithm’s input from analysis, else we’d need at least that much space no matter the algorithm!

To be fair, the number of bits we need to store i might technically depend on n. Indeed, the bigger n is, the more bits we might need. But let’s not worry about bits.

(3 points.) Recall Week 3’s pseudocode for selection sort, whose time complexity was in O(n²):
```
For i from 0 to n-1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item
```
Assuming its input is of size n, what’s the space complexity of selection sort, using big-O notation? In no more than three sentences, why?
(3 points.) Recall Week 3’s pseudocode for merge sort, whose time complexity was in O(n log n):
```
If only one number
    Quit
Else
    Sort left half of numbers
    Sort right half of numbers
    Merge sorted halves
```
Assuming its input is of size n, what’s the space complexity of merge sort, using big-O notation? In no more than three sentences, why?
(3 points.) Consider the (recursive) implementation of sum, below, which returns the sum of all of the numbers from 1 through n.
```
int sum(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else
    {
        return n + sum(n - 1);
    }
}  
```
In no more than three sentences, why is the space complexity of this implementation of sum in C in O(n)? Assume no compiler optimizations.
(3 points.) Complete the reimplementation of sum, below, in C in such a way that your reimplementation’s space complexity is instead in O(1). Assume that n will be non-negative.
```
int sum(int n)
{
    // TODO
}
```