lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Wed, Oct 7, 2020, 05:53 Egor Skriptunoff <> wrote:
On Wed, Oct 7, 2020 at 3:20 AM Luiz Henrique de Figueiredo wrote:
We have received no feedback on Lua 5.4.1.
Does that mean that everything is perfect?

Amortized cost of table insertion is O(n)
It looks like a bug.
Although the manual promises nothing about Lua interpreter speed,
something like O(logn) is usually required for table operations.

Amortized cost of a single insert is O(1), and for 'n' operations is O(n). A single insert has a worst case cost of O(n) but the are very few of those. 

The strategy of doubling the size of a table each time you run out of space is essential for this behavior. You will only copy/rehash entries 2*n times worst case to grow a table to 'n' entries.