Introduction to Space Complexity
Have you ever wondered about the amount of space needed by an algorithm or a piece of code, to execute to completion? Are you curious about how complex a code or algorithm might be from execution space perspective? And most importantly, do you always feel like comparing the possible execution space of two different piece of code giving same output? If yes, then read on…
What is Space Complexity?
Let’s start with the most basic question, how do we compare the execution space needed by two piece of code giving same output. Simply, which code is going to take less space?
The amount of memory needed to solve the computational problem as a function of the input is known as the space complexity of an algorithm or a piece of code. In other words, it is the memory needed by an algorithm up until the point at which it is fully executed.
The exact space complexity of an algorithm can depend on the specific implementation and the programming language used, as well as constant factors such as the size of pointers and the size of data types.
Recursive algorithms can have significantly different space complexity compared to iterative algorithms, as they require additional memory to store the call stack.
Space and time complexity are often intertwined, and optimizing one can impact the other. For example, using a more space-efficient data structure may reduce memory usage, but increase the time complexity.
Space complexity can be optimized by using more space-efficient data structures, reducing the number of temporary variables, and reusing memory whenever possible.
When designing algorithms, it’s important to consider the trade-offs between space and time complexity to find the best overall solution for a particular problem.
Space complexity is an important factor to consider when implementing algorithms in real-world systems, as it can impact the memory requirements and scalability of the system.
A related term called auxiliary space implies the space used by the algorithm, other than the space used by the input. The additional or temporary space used by an algorithm is known as auxiliary space. The amount of space an algorithm uses overall in relation to the size of the input is known as its space complexity.
Space Complexity = Input Space + Auxiliary Space A similar concept you may like to read is Time Complexiy of Code.
Why to use Space Complexity?
- Used to determine which algorithm, out of all the algorithms, is the most optimal from the requirment of memory perspective.
- Many a times programmers have memory constraint for the platforms they are developing the application for.
Similar to time complexity, which is frequently described in Big O notation, space complexity is also described as O(1), O(n) etc, in terms of Big O notation, where n is a property of the input that affects space complexity.
What is Asymptotic Notations?
Asymptotic notations are mathematical notations used to express the running time of an algorithm or the space required by the method when the input tends towards a high value.
There are three types of asymptotic notations:
Big-O (O) notation
Big Omega ( Ω ) notation
Big Theta ( Θ ) notation
Therefore, lets discuss what is Big O notation in the next section.
What is Big O Notation?
We can represent measurements of space complexity using a variety of notations. Big-O notation is the most popular, thus that will be our main emphasis.
The complexity’s upper bound is described by the Big-O notation. Therefore, it provides the worst-case scenario for the complexity growth rate of an algorithm. We can predict that the size of this algorithm will not increase any faster than the function represented by Big O notation, although it may increase slightly more slowly.
Big O Notation estimates how much space an algorithm will take to run as the input size grows. In other words, it establishes the worst-case space complexity of an algorithm. The Big O Notation in data structures is used to express an algorithm’s maximal space taken.
For instance, 0(1) space complexity denotes complexity with constant space. This indicates that the code will take the same amount of space regardless if you increase the input size, n.
0(n), which represents linear space complexity, is similar. This means that when you raise the size of the input, n, the space it takes for the code to run will grow proportionally as well.
We’ve covered enough theory; let’s move on to some real Python code to better grasp the space complexity of the majority of loop cases.
Space Complexity with Examples in Python
In this section we will discuss the space complexity of while loops written in python programing language.
Note that here variable n indicates the input size and other variables like j and output contibute to auxiliary space.
Loop with Space Complexity – Constant Space – O(1)
Let us create a while loop in python such that, the number of space taken by loop is indpendant of input size n. The code is written below:
# Example of Loop with Space Complexity O(1)
output = 0; j = 1; n = 10
while j < n:
output = output + j
j = j + 1
print(output) In the above code example input value ‘n’ is constant which will take the space of O(1). The auxiliary space is also O(1) becuase ‘j’ and ‘output’ are also constants.
Hence total space complexity is O(1) + O(1) = O(1).
Loop with Space Complexity – Linear Space – O(n)
# Example of Loop with Space Complexity O(n)
myList = {1,2,3,4,5}
output = 0
for item in myList:
output = output + item
print(output)In the above code example input value ‘myList’ is a variable length which will take the space of O(n). Input space taken by this loop is proportional to the length of the list.
The auxiliary space is also O(1). Becuase ‘item’ and ‘output’ are constant length so taking same amount of space even if list size increases.
Hence total space complexity is O(n) + O(1) = O(n).
Space Complexity Example-Logarithmic – O(log n)
Quick Sort algorithm has O(log n) space complexity. Quick Sort is a sorting algorithm that employs the divide-and-conquer strategy. In quick sort, we select one element as a pivot and partition the array around that pivot. We sort our array by repeating this procedure for each partition.
Conclusion
The amount of memory needed by an algorithm to operate completely, including the input values required to get the result, is referred to as its space complexity. Before being employed, an algorithm must be kept in memory. Memory can be used in a variety of ways. Variables, programme execution, etc. are a few examples.
In this article, we dicussed space complexity with example code in python. Knowing the time complexity and space complexity is necessary for creating any efficient algorithms. The space complexity can be optimised, making the code more effective and swift.
Most often, as speed is increased, memory utilisation increases and vice versa. In conclusion, we cannot strive for the highest combined time and space efficiency. Most frequently, one of these must be sacrificed in order to meet our needs. Sometimes we can strike a good balance.
