title: What is the time complexity of searching JavaScript object keys?
body: <p>I am using a JavaScript object as a dictionary, and wanted to make keys case-insensitive. I used <code>Object.defineProperty()</code> to implement this:</p>
  
  
  
  <pre class="lang-js prettyprint-override"><code>Object.defineProperty(Object.prototype, "getKeyUpperCase", {
      value: function(prop) {
          for (var key in this) {
              if (key.toUpperCase() === prop.toUpperCase()) {
                  return this[key];
              };
          };
      },
      enumerable: false
  });
  </code></pre>
  
  <p>What is the time complexity of searching an object via key in JavaScript? I'm expecting the dictionary to hold around 1 million keys.</p>
  
  <p>To me it looks like worst case would be <code>O(n)</code>, best case would be <code>O(1)</code> and average case would be <code>O(n/2)</code>. Is this correct?</p>
  
  <p>Would it be substantially more efficient to retrieve the object's keys as an array (<code>Object.Keys(dictionary).map(function(key) return key.toUpperCase()).sort()</code>) to check if the key exists? Am I correct in saying that the average time complexity of this operation is <code>O(log n)</code>?</p>
  
  <p>Usage of the dictionary is along the lines of this:</p>
  
  <pre class="lang-js prettyprint-override"><code>var dictionary = {/* some million keys or so */};
  var oldKey = someSmallArray[i];
  var newValue = dictionary.getKeyUpperCase(oldKey.trim().toUpperCase());
  </code></pre>