Re: pairs(t, skey) and ipairs(t, skey)

[Tim Hill <drtimhill@...>]

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).

My original suggestion was O(n) in the sense of having a small fixed overhead per new item in the table, which would be O(1) in your terminology. I avoided the max issues by the slight change to the definition of sequence.

--Tim