Space Complexity

In addition to runtime complexity, we can also consider the space complexity of an algorithm. The space complexity refers to, basically, how much memory an algorithm requires. We can also use big O notation to describe space complexity.

For example, take the classic fibonacci algorithm:

func fibonacci(n int) {
	if n <= 1 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

In this case, the space time complexity is O(2n) (exponential), because the amount of calls grows exponentially as the size of the input grows. Each recursive call to fibonacci is stored in memory, so the amount of memory used grows exponentially with the size of the input.