I'm a Systems Reliability and DevOps engineer for Netdata Inc. When not working, I enjoy studying linguistics and history, playing video games, and cooking all kinds of international cuisine.
OK, now I'm curious: Does the ECMA standard actually guarantee Θ(n) time complexity for instantiation of a Set from an arbitrary Array?
I could easily see all the implementations happening to have Θ(n) time complexity for it, but unless the standard says that it always will be, you can't really say it's Θ(n) without specifying an implementation.
So the first method is Θ(n log(n)), Mozilla and Google's implementations are a Merge Sort and Timsort respectively.
As for the the ECMA standard for a Set, internally they're recommended to use hash tables (or something similar). Insertion in hash tables run at Θ(1), so an array of n elements would reasonably be Θ(n).
Well yes, but worst case of hash tables is linear. If you don't mind the space you can create an auxiliar array and mark the positions. This is the "same" idea used in the hash table but it guarantees a O(n) solution. This solution requires O(n) extra space complexity, but hash table in worst case is also O(n) ( when all numbers are different)
OK, now I'm curious: Does the ECMA standard actually guarantee Θ(n) time complexity for instantiation of a
Setfrom an arbitraryArray?I could easily see all the implementations happening to have Θ(n) time complexity for it, but unless the standard says that it always will be, you can't really say it's Θ(n) without specifying an implementation.
So the first method is
Θ(n log(n)), Mozilla and Google's implementations are a Merge Sort and Timsort respectively.As for the the ECMA standard for a Set, internally they're recommended to use hash tables (or something similar). Insertion in hash tables run at
Θ(1), so an array ofnelements would reasonably beΘ(n).Well yes, but worst case of hash tables is linear. If you don't mind the space you can create an auxiliar array and mark the positions. This is the "same" idea used in the hash table but it guarantees a O(n) solution. This solution requires O(n) extra space complexity, but hash table in worst case is also O(n) ( when all numbers are different)
Good point, the fact that it's built-in doesn't necessarily mean faster.