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?
Comments
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…
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.
Isn't it O(k) for PATRICIA tries, where k is an average key length?
E.g., see https://en.wikipedia.org/wiki/Radix_tree#Comparison_to_other_data_struc…
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.