lua-users home
lua-l archive

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


> Amortized cost of table insertion is O(n)
> http://lua-users.org/lists/lua-l/2020-09/msg00178.html
> It looks like a bug.
> Although the manual promises nothing about Lua interpreter speed,
> something like O(logn) is usually required for table operations.

I don't think it is wise to expect O(log n) as the worst case for table
operations. Most hash tables have a worst case O(n) for insertion and
retrieval, due to collisions.

-- Roberto