Complexities of Space
Not only can you use bigO 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 n1
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^{2}):
For i from 0 to n1 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 bigO 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 bigO 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 from1
throughn
.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 thatn
will be nonnegative.int sum(int n) { // TODO }