Lookup Time Complexity of a Global

If I were trying to access an index of a global variable, what time complexity would this operation have? My understanding of languages like Java/C++ is that arrays are stored as blocks of memory so that x[15] would have a lookup time complexity of O(1) because it just goes to (address of the array + 15) and retrieves the value stored there.

How does this work in Cache where the index of a variable isn't necessarily an integer value? If I were to have a variable like the following:

x("Adam") = "Red"

x("George") = "Blue"

x("Bryan") = "Green"

etc...

Would the lookup operation scale with the size of the array such that the variable is iterated through until the given index meets the current index, yielding a O(n) lookup? Or is this done a different way?

  • + 1
  • 0
  • 253
  • 4
  • 1

Answers

The overhead of looking up a node is O(ln n), the structure is based on a B+ tree. Some information here:

 

http://docs.intersystems.com/latest/csp/docbook/DocBook.UI.Page.cls?KEY=...

https://en.wikipedia.org/wiki/B%2B_tree

 

Does that hold true for in-memory arrays as well? Or only for globals on disk?

In memory arrays use a ptrie format and are also O(ln n) lookup time.

You are basically correct. We do try to minimize branch points in the tree, so an array with one subscript array("very long subscript") only has a single element in it rather than one per byte associated with the subscript. So this reduces it to <k depending on the distribution of the keys.