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

[Tim Hill <drtimhill@...>]

On Oct 6, 2013, at 4:41 PM, Philipp Janda <siffiejoe@gmx.net> wrote:

> 
> I think it is customary to specify big-O information for a single call of the operation you are interested in.
> 
> So, table insertion is O(1), sequence validation is O(n). I think the confusion started because Roberto tried to point out that constant overhead during table insertion ends up being of the same complexity as a sequence validation if you consider the combined operation, because you do n O(1) inserts and one[*] O(n) validation. And the performance of sequence validation was the subject we were talking about at that time ...
> 
>  [*]: or at least a fixed number not dependent on 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.
>> 

i think we're saying the same thing from a different viewpoint .. there is a certain amount of work to be done, and it can either be done late (at # time, with O(n) cost) or early (at insert time, with n * O(1) cost). Both have (well known) trade-offs of course.

I have not looked at the code in detail, but I suspect the current # behavior is more or less a "freebie" side-effect of how the table internals work, hence it's odd behavior with non-sequence tables.

--Tim