On Oct 6, 2013, at 2:24 PM, Dirk Laurie <dirk.laurie@gmail.com> wrote:
2013/10/6 Tim Hill <drtimhill@gmail.com>:
I think there is some confusion of scope here. The implementation
of the # function is (not surprisingly) O(1) but the entire set of logic
to *realize* that behavior is O(n) since there is code for each
__newindex() call. That was the point of my original post, since
Roberto had raised concerns that my suggested design was O(n) ..
though, like Dirk's design, it was O(n) for __newindex() calls, and
was O(1) for the actual call to #.
My code is O(1) per __newindex call. Merely storing something in
a table is also O(1) per call, so O(1) per call is optimal.
There's a once-only startup pass over the whole table, which
amortizes to O(1) per table entry.
If you wish to track the largest index actually present in the table,
that would be O(n) per __newindex, unless you invest in maintaining
a priority queue.
… so it's O(1) per call, which is O(n) for n entries, which is O(n).
