Big O notation for helper methods

One piece of information that I think would be useful to add to JavaScript documentation is to show what the Big O time complexity of the functions are, especially with Arrays.

Some may be different across browsers but I think it would be helpful for many people.

1 Like

Hi @Peter_Wiebe! Thanks for your suggestion!

Seems tricky, since as you say, it may vary across browsers. MDN documents the API, but (mostly) not the implementations, except as they vary from the spec. And it would probably require delving into source code to figure out.

@fscholz ‚Äď Your thoughts?

Well, all array iteration methods have a time complexity of O(N), with chains of them always having O(N * M), where M is the number of chained methods, since they’re all eagerly evaluated.

The Iterator Helpers proposal adds lazily evaluated methods to Iterator instances, equivalent to the array iteration methods, which can have a much lower Big O time complexity, as the resulting pipeline is processed fully for each element.

This came up ages ago and I thought we had discussed it, but I’m unable to find a discussion now. Prior request: https://bugzilla.mozilla.org/show_bug.cgi?id=1309784

I think an explanation what Big O or algorithmic complexity is, would be nice to have somewhere on MDN. It might be difficult to always have a Big O notation for built-in functions as it may differ in engines and the spec doesn’t dictate this. So, I don’t know really. Maybe there are common pitfalls and we could demonstrate how to reduce complexity by having some good/bad code examples. I think that’s more beneficial than adding (another) cryptic information piece to reference pages that not everyone understands and that might not always be true.

As a new user of the Mozilla platform I think this is a really good idea, I understand there are complexities with it but even giving it a base line could be useful ? I have contributed to documentation and have explored the Mozilla code base and forums and feel this could be a helpful and interesting addition.

1 Like

The specs do mandate an algorithm, and Big O notation is directly linked to the algorithm being used.

That said, this probably only really makes sense for Array iteration methods.

2 Likes

OK. We could experiment with adding it to Array iteration methods and then see if we get any more reader feedback for or against it.

2 Likes

Appreciate that you are considering this. For context I have searched which sorting algorithm is being used by the browsers, which has been useful in some interviews that I have had in the past, only to be lead to SO to find the answer.