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

[Roberto Ierusalimschy <roberto@...>]

> 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