News for hackers. Stuff that matters.

A comment on Removing Array Duplicates. Parent comment

Re:Removing Array Duplicates by bakhy on Friday April 12, 2019 @09:49AM (#19644751)
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!
[ Parent | on HN ]
Re:Removing Array Duplicates by gusmd on Friday April 12, 2019 @11:32AM (#19645706)
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...

[ Parent | on HN ]