Re: Speed of # operator (Was: ipairs in Lua 5.3.0-alpha)

[Dirk Laurie <dirk.laurie@...>]

2014-08-14 13:09 GMT+02:00 Jan Behrens <jbe-lua-l@public-software-group.org>:

> I'm aware of the fact that t[#t + 1] = v is a common idiom
>    and that the usage of the # operator has a complexity of
>    O(n*log(n)) when used in a loop to fill a table. In many
>    programs that doesn't matter (it's still fast enough and
>    filling a table is O(n*log(n) anyway), so I usually don't
>    care to optimize here.

Actually, filling a table is O(n). It is true that there may be
O(log n) reallocations, but these are all doublings, so the
total time is like 1+2+4+8+...+2^k = 2n where n=2^k.