0

I'm using JavaScript, but I assume this is relevant for many computer languages.

Why lookup in obj(Object) in the following case is O(1)? Isn't it should be O(n)? Can anyone explain it to me please, like provide an actual, low-level explanation why this isn't O(n)?

let arr = ['m', 'k', 'b', 'z']
let obj = { 'a': true, 'b': true, 'c': true}

for (let i = 0; i < arr.length; i++) {
  if ( obj[arr[i]] ) {
    return true
  }
}

The above time complexity is considered as O(n), but hopefully you can see why this question is rising for me, because in order to find(for example) if obj['b'] === arr[2] (this is exactly what I do with the condition if ( obj[arr[i]] )), I will naturally think that it should go through all of the properties of obj and compare, but isn't that looping of it own kind, so to say overall it should be O(n^2)? Again, if not, please explain why, why it doesn't loop, but able to pick it immediately(O(1)).

totezy
  • 1
  • 1
    Objects are hashes. It would be EXTREMELY bad if any property lookup was `O(n)` - it would more or less defeat the purpose of even using objects, since there would be such a significant loss of performance. – VLAZ Oct 18 '20 at 10:28
  • https://stackoverflow.com/questions/15469795/why-hashmap-lookup-is-o1-i-e-constant-time – Evan Trimboli Oct 18 '20 at 10:29
  • if the language implementation creates a jump-table, you understand everything. For example see this: https://en.wikipedia.org/wiki/Branch_table#Jump_table_example_in_C you must execute some arithmetic (for address calculation) and jump to needed code. This is O(1) time – sarkiroka Oct 18 '20 at 10:34
  • Yes, I've got it, thank you. – totezy Oct 18 '20 at 10:36

0 Answers0