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

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_Array https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...