Linked-list duplicate-checking put is quadratic; expect a timeout at large n
@matnvd▲ 1 net votes
A linked-list symbol table that walks the whole list on every put for duplicates is O(n^2) overall. In testing, 50,000 inserts took about 10 seconds and 500,000 would exceed a 5-minute limit. This is expected behavior, not a bug, so document the timeout rather than debugging it. A hash table that resizes on load factor handled 500,000 inserts in about 0.13 seconds.