1

I am using a JavaScript object as a dictionary, and wanted to make keys case-insensitive. I used Object.defineProperty() to implement this:

Object.defineProperty(Object.prototype, "getKeyUpperCase", {
    value: function(prop) {
        for (var key in this) {
            if (key.toUpperCase() === prop.toUpperCase()) {
                return this[key];
            };
        };
    },
    enumerable: false
});

What is the time complexity of searching an object via key in JavaScript? I'm expecting the dictionary to hold around 1 million keys.

To me it looks like worst case would be O(n), best case would be O(1) and average case would be O(n/2). Is this correct?

Would it be substantially more efficient to retrieve the object's keys as an array (Object.Keys(dictionary).map(function(key) return key.toUpperCase()).sort()) to check if the key exists? Am I correct in saying that the average time complexity of this operation is O(log n)?

Usage of the dictionary is along the lines of this:

var dictionary = {/* some million keys or so */};
var oldKey = someSmallArray[i];
var newValue = dictionary.getKeyUpperCase(oldKey.trim().toUpperCase());
Matheus Avellar
  • 1,507
  • 1
  • 22
  • 29
Zach Smith
  • 8,458
  • 13
  • 59
  • 133
  • Just a note you wouldn't need to search every key... you would only test all possible cases of the a single key, ie `this['name']` vs `this['Name']` vs `this['NAme']` and so on. And further you could use a [Proxy](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Proxy) of your dictionary, instead of the the dictionary directly, to make sure each key set is always lowercase / uppercase when being set / get – Patrick Evans Sep 24 '17 at 14:32
  • Thanks. I didn't think of that. Would that be quicker than what I have done? I don't know how dictionaries are implemented in JavaScript yet, so I don't know how to compare performance – Zach Smith Sep 24 '17 at 14:34
  • It would depend on the length of the key being tested. As you would need to create each possible case of the key and then test them. And that number could get quite large itself. I personally would go the Proxy route (if using supported browsers) as there would be no searching at all you would just be using `this[key.toLowerCase()]` in both setter and getter. – Patrick Evans Sep 24 '17 at 15:08
  • Would it be possible to override the getter of a particular object to always return capital case? i.e instead of a proxy, just overriding the getter. – Zach Smith Sep 24 '17 at 15:15
  • 1
    Object's do not have a wildcard getter / setter, which is why you would need to use the Proxy, [Proxy example](https://jsfiddle.net/y0f5mdeo/) – Patrick Evans Sep 24 '17 at 15:16
  • Thanks again @PatrickEvans. I'm using node.js. with a library called pkg that creates a .exe. https://stackoverflow.com/questions/7891937/is-it-possible-to-implement-dynamic-getters-setters-in-javascript. This example works on node.js – Zach Smith Sep 25 '17 at 06:34

1 Answers1

2

First, some thought about big-O notation:

This mathematical tool tries to grab the concept of "order of magnitude" in a long-term scenario. As size grows constants get less and less importance. Hence calculating big-O usually we don't bother with constants.

That's why O(n/2) = O(n).

So the linear lookup has O(n) time complexity.

About the sorting:

The sort algorithm of JavaScript is browser dependent but you can assume an O(n log n) complexity for that. Usually, it doesn't worth to sort for only one lookup but if you can sort only once and you can make several lookups maybe it is worth it. By the way, If you have a sorted list to search maybe you could try to implement binary search to speed up your searching.

Zsolt V
  • 517
  • 3
  • 8