Worst Case and Space complexity

Worse Case

function contains(haystack, needle) {
// Does the haystack contain the needle?
for (let i = 0; i < haystack.length; i++) {
if (haystack[i] === needle) {
return true;
}
}
return false;
}

Here we might have 100 items in our haystack, but the first item might be the needle, in which case we would return in just 1 iteration of our loop.

Space complexity: the final frontier

Sometimes we want to optimize for using less memory instead of (or in addition to) using less time. Talking about memory cost (or "space complexity") is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we're allocating.

This function takes O(1)O(1) space (we use a fixed number of variables):

function sayHiNTimes(n) {
for (let i = 0; i < n; i++) {
console.log('hi');
}
}

Usually when we talk about space complexity, we're talking about additional space, so we don't include space taken up by the inputs. For example, this function takes constant space even though the input has nn items:

function getLargestItem(items) {
let largest = -Number.MAX_VALUE;
items.forEach(item => {
if (item > largest) {
largest = item;
}
});
return largest;
}

Sometimes there's a tradeoff between saving time and saving space, so you have to decide which one you're optimizing for.