Time complexity of finding a key by value in Javascript
I know that looking up a hash value by key is O(1)
(constant time) but is it the same if you find the key that has a certain value? I'm looking up the key using:
const answer = Object.keys(dict).find(key => dict[key] === 1);
dict
is an object that has integer keys.
That's O(n)
time complexity, since you're performing a linear search on an array (the array returned by Object.keys
). At worst, the item you want will be the last item in the array (or it won't be in the array at all), which would require n
operations to determine (n
being the length of the array) - hence, it's O(n)
time.