Big O Notation
Overview of Space Complexity
Big O notation provides Software Engineers a way in which to discuss algorithms and how they perform. Big O notation allows for a simplified way to answer the question of; which solution will the computer run faster? and which uses the least amount of computer memory? These two questions fall under two different Big O notation complexities, Time Complexity and Space complexity, respectively. This blog will focus on the second question of computer memory, which falls under the category of Space Complexity. If you are unfamiliar with Time Complexity, I recommend first reading my previous blog post found here.
What is Space Complexity?
Space Complexity is defined as, “… a measure of the amount of working storage an algorithm needs. That means how much memory, in the worst case, is needed at any point in the algorithm. As with time complexity, we’re mostly concerned with how the space needs grow, in [Big-O] terms, as the size N of the input problem grows” (Riesbeck).
As Software Engineers, we may want to write our algorithms to optimize for Space Complexity rather than Time Complexity as there can be significant tradeoffs. To tell how much computer memory our algorithm takes up, we don’t include the computer memory taken up by inputs but instead count, “ …how much additional memory do we need to allocate in order to run the code in our algorithm?” (Steele).
When trying to determine the Space Complexity of an algorithm we can use the following table as our guide.
Next, we will look at the different types of Big O notation complexities and provide an example algorithm for each.
O(1)
From our discussion on Time Complexity, we determined that an O(1) means that an algorithm has a constant runtime. Similarly, when an algorithm has a Space Complexity of O(1) it means that our algorithm has constant space. In the below example, we have a function that prints numbers starting at one up to some number n.
function printNumbers(n) {
for (let i = 1; i <= n; i++){
console.log(i);
}
}printNumbers(3)Output: 1
2
3
In the above example, we do not count the inputs n, so the only item taking space is our i variable. Since the i variable is a primitive type, number, it has a constant space of O(1). Moreover, although the Time Complexity is O(n) because the runtime is increasing in a linear fashion with n, the Space Complexity is only O(1) because in the loop, the value of i is simply incrementing from one number to the next.
O(n)
An O(n) means that the Space Complexity of an algorithm is linear. Meaning, that as the variable grows, so does the Space Complexity in a 1:1 fashion. From our summary table, we can see that strings, arrays, and objects have Space Complexities of O(n). Let’s look at an example where we take in an array and create a new array where each element is one less than what it is in the initial input array.
function subtractOne(array) {
let newArray = [];
for( let i = 0; i < array.length; i++) {
newArray.push(array[i] -1);
}
return newArray
}subtractOne([2,3,4])Output: [1,2,3]
Looking at the above algorithm, there are a couple of different items that have Space Complexity. The variable declarations of newArray and i which both initially have an O(1); however, the line that makes this algorithm have a Space Complexity of O(n) is the newArray.push(array[i] -1). This line pushes an element into our newArray variable for each element in the input array. So, the space increases as n increases, which means that the variable increases in a linear fashion or O(n).
Thank you for taking the time to learn more about Big O notation and Space Complexity. Be on the lookout for the next blog, where we discuss the Big O of objects and their methods.
Resources
Steele, C. (n.d.). JavaScript Algorithms and Data Structures Masterclass. Online Course.
Riesbeck, Chris. EECS 311: Space Complexity, Northwestern University, courses.cs.northwestern.edu/311/html/space-complexity.html.
“Big O Notation: Interview Cake.” Interview Cake: Programming Interview Questions and Tips, www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity.
