On Fri, Aug 15, 2014 at 5:01 AM, Roberto Ierusalimschy
<roberto@inf.puc-rio.br> wrote:
This is not correct, as Dirk already pointed out. (You do not move n/2
elements log(n) times; you move 1 element, then 2 elements, then 4
elements, etc. The lenght of that sequence is log(n), but you should
not mulitply that by n.)
-- Roberto
To clarify -- the sum of that sequence is:
sum[i=0..log_2(n)](2^i)
Which, plugged into WolframAlpha, yields 2n-1, which is O(n).
That is, in the worst case scenario where you're copying the contents
every time you have to expand, it's still just O(n) total copies!
/s/ Adam