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

[Coda Highland <chighland@...>]

On Fri, Aug 15, 2014 at 5:01 AM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
>> To fill a table with n elements you will on average move n/2
>> elements to new places
>> log(n) times which is exactly O(n*log(n)).
>
> This is not correct, as Dirk already pointed out. (You do not move n/2
> elements log(n) times; you move 1 element, then 2 elements, then 4
> elements, etc.  The lenght of that sequence is log(n), but you should
> not mulitply that by n.)
>
> -- Roberto

To clarify -- the sum of that sequence is:

sum[i=0..log_2(n)](2^i)

Which, plugged into WolframAlpha, yields 2n-1, which is O(n).

That is, in the worst case scenario where you're copying the contents
every time you have to expand, it's still just O(n) total copies!

/s/ Adam