Re: Speed of # operator (Was: ipairs in Lua 5.3.0-alpha)
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Speed of # operator (Was: ipairs in Lua 5.3.0-alpha)
- From: Roberto Ierusalimschy <roberto@...>
- Date: 2014年8月15日 09:01:16 -0300
> 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