DEV Community

Discussion on: Time complexity Big 0 for Javascript Array methods and examples.

Collapse
 
redbar0n profile image
Magne • Edited

What reference did you lean on to find their time complexity?
If their complexities are assumed or inferred, I'm not sure the assumptions hold, since each engine implements JS arrays differently. See: stackoverflow.com/a/61713477/380607

PS: I think it would be wise to mention that .some() is only O(n) in the worst case, but rather O(k) normally, where k is the index to be found, which on average will be the middle (median) index, so k = n/2. While a factor of n, it is different than other O(n) functions which necessarily will have to go through the entire array and thus amount to the full n.

Collapse
 
rokal profile image
Roland Kalmogo

Big O is already the worst case. otherwise, we have Omega and Theta

Collapse
 
shksa profile image
sreekar

Big O is not the worst case. Big O tells you the upper bound growth rate function. That's it. Worst case tells you a specific example of input which would make the algorithm run for the longest time. Big O can be used to describe the upper bound in worst case, average case, best case. Both are orthogonal.

Thread Thread
 
_mikeusa profile image
Mike

This may be accurate, but for all practical purposes of conceptual understanding; upper-bound ≈ worst case.

It's simpler to describe Big-O vs Big-Theta vs Big-Omega and also stay away from little-o. Again, this is for simplistic terms and anything outside a data scientist and seasoned engineer should probably stick to the simplified understanding as colloquial terms.

This is targeting entry level devs, which I think does service in how it describes the topic:
educative.io/blog/a-big-o-primer-f...