On Wed, Oct 7, 2020 at 8:39 PM Roberto Ierusalimschy wrote:
> 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.
It is true that it is always possible to create a sequence of
table operations to exploit collisions in a hash table.
But the bug discussed here is not about collisions.
The keys in my example are the natural sequence of numbers 1,-1,2,-2,....
It is obviously NOT a maliciously crafted sequence to exploit hash table
collisions.
The bug is due to table rehashing might happen VERY often,
and each rehash costs O(n), hence the quadratic time complexity.
In a correct implementation it is wise to expect O(n) table operations done
before the next rehash happens.
