4 ms·
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)
by kevinventullo 8y 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)
- bakhy 8y agoI 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!
- gusmd 8y agoYep! 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_Array https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...