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

[Tim Hill <drtimhill@...>]

On Oct 6, 2013, at 11:10 AM, Coda Highland <chighland@gmail.com> wrote:

> On Sun, Oct 6, 2013 at 10:54 AM, Tim Hill <drtimhill@gmail.com> wrote:
>> 
>> 
>> Both are O(n) execution time (we're not talking about memory overhead).
>> 
>> --Tim
> 
> Algorithmically speaking, both approaches are O(1) per access on top
> of whatever algorithmic complexity the underlying implementation has.
> It has no impact on the algorithmic complexity of any algorithm that
> the change is applied to.
> 
> /s/ Adam
> 

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 point was that I didn't see any way to handle # sanely that wasn't O(n) in the sense of needing some overhead for each key/value pair inserted (or deleted) from the table.

--Tim