Time complexity of Dynamic Array via repeated doubling

Question

When we implement dynamic array via repeated doubling 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?

But

 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

Answer 1

You're on the right track with your sum, but you have too many terms in it. :-)

The array will double in size when it reaches any size that's a power of two. Therefore, if the largest power of two encountered is 2^k, the work done is

2⁰ + 2¹ + 2² + ... + 2^k

This is the sum of a geometric series, which works out to

2⁰ + 2¹ + 2² + ... + 2^k = 2^k+1 - 1 = 2 · 2^k - 1

In your analysis, you wrote out this summation as having n terms it, ranging up to 2ⁿ. This would be the right summation if your array had 2ⁿ elements in it, but that's exponentially too many. Rather, since your array has n total elements in it, the maximum term in this sum is 2^{lg n}. Plugging that in gives

2 · 2^{lg n} - 1 = 2n - 1 = Θ(n)

Therefore, the total work done comes out to Θ(n), not Θ(2ⁿ).

Hope this helps!