Explain your understanding of “Space Complexity” with examples

Space complexity means the amount of space the algorithm needs to run.

Example 1: Sorting-Algorithms
All sorting algorithms need at least O(n) space to save the list (of length n) they have to sort

1. Bubblesort (and most other sorting algorithms too) can work in-place, this means that it needs no more space as it needs to save the list. (just searching two elements in the wrong order and swaping them)
2. Stupid-Sort lists all permutations of the input list (and saves them) and then searching the sorted one. Since there are n! permutations this algorithm needs O(n * n!) space.

Example 2: Number representation
A number n can be saved in different ways:

1. binary (or any other base ≥2): this needs O(log n) space, due to n = 2log n
2. unary: here you write n as a sum of ones (n = 1 + 1 + 1 + ... + ... + 1) and you have to save every one. So this needs O(n) space, due to n = n ⋅ 1.