When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the new one? Correct?
So to compute the complexity we have 1 + 2 + 4 + 8 + .... number of steps? Correct?
1 + 2^1 + 2^2 + .... + 2^n = (2^(n-1) - 1) ~ O(2^n).
However it is given that
1 + 2 + 4 + ... + n/4 + n/2 + n ~ O(n).
Which one is correct? And why? Thanks