Note → Time and space complexity are high-level measures of scalability. They don’t measure the actual speed of the algorithm itself.

Space Complexity

The time complexity of an algorithm isn’t the only performance metric against which algorithms are ranked. Another important metric is its space complexity, which is a measure of the amount of memory it uses.

So basically, It is made up of Auxiliary space (extra or temporary space) and Input space (all possible inputs).

fun printSorted(numbers: List<Int>) {
    val sorted = numbers.sorted()
    for (element in sorted) {
        println(element)
    }
}

Since numbers.sorted() produces a new list with the same size of numbers, the space complexity of printSorted is O(n)

While the above function is simple and elegant, there may be some situations in which you want to allocate as little memory as possible. You could rewrite the above function like this:

fun printSorted(numbers: List<Int>) {
   
    if (numbers.isEmpty()) return
    
    var currentCount = 0
    var minValue = Int.MIN_VALUE
   
    for (value in numbers) {
        if (value == minValue) {
            println(value)
            currentCount += 1
        }
    }
    while (currentCount < numbers.size) {
        
        var currentValue = numbers.max()!!
        for (value in numbers) {
            if (value < currentValue && value > minValue) {
                currentValue = value
            }
        }
        
        for (value in numbers) {
            if (value == currentValue) {
                println(value)
                currentCount += 1
            }
        }
        
        minValue = currentValue
    }
}

The above algorithm only allocates memory for a few variables. Since the amount of memory allocated is constant and does not depend on the size of the list, the space complexity is O(1).

Tradeoff → This is in contrast with the previous function, which allocates an entire list to create the sorted representation of the source array. The tradeoff here is that you sacrifice time and code readability to use as little memory as possible. This is common in a problem since a problem cannot have both low computing time and low memory consumption. you either use more memory and solve the problem more quickly or use more time to solve the problem but with limited memory.

Note → The best algorithm/program should have the minimum space complexity. The lesser space used, the faster it executes.