1

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.

Improve this question
1
  • No, that would be O(n) time complexity. Commented Jan 18, 2022 at 22:24

1 Answer 1

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

And even in the best case, where the target value is the first item, Object.keys() will have a time complexity of O(n)
@Bergi so would it be more efficient to iterate with a for...in loop rather than using Object.keys? (note I'm asking about raw time efficiency in ms, not big O)
Probably. On the other hand, js engines might be able to optimise the Object.keys() pattern into an iterator as well - you'd have to benchmark it.
Alright, interesting - thanks!

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.