Hacker News new | ask | show | jobs
by bakhy 2626 days ago
This is what I'd do too, and it is quite strange that it was dismissed like that. Maybe because it's not as much fun :)

BTW I believe it may be a bit more than just O(n) time on the whole. If your hash-table is auto-growing, you'll have to pay for its resizing. And OTOH if it's sized up front, then you'll have to allocate something proportional to the size of the full array, not just to the number of distinct elements.
1 comments
kevinventullo 2626 days ago
As long as the resizing e.g. doubles the size each time, the total running time will still be O(n). Basically because

  1+2+4+...+2^k = O(2^k)
link
bakhy 2626 days ago
I think I get it. With doubling, the sum of all the work done for resizing is roughly (written chonologically backwards): n/2 + n/4 + ... ~= n, and O(n) + O(n) is still O(n). Thanks!
link
gusmd 2626 days ago
Yep! This is generally referred to as "amortized linear time". It's the difference between considering the cost "per operation" vs. "per algorithm". The former is technically correct (as an upper bound), but too pessimistic when you consider the algorithm as a whole.

See https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...

link