DEV Community

Cover image for Worst Case and Space complexity
Sakshi
Sakshi

Posted on

1 1

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more