Time complexity of Dynamic Array via repeated doubling
arrays, big-o, complexity-theory, dynamic-arrays, time-complexity
Solution
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 2k, the work done is
20 + 21 + 22 + ... + 2k
This is the sum of a geometric series, which works out to
20 + 21 + 22 + ... + 2k = 2k+1 - 1 = 2 · 2k - 1
In your analysis, you wrote out this summation as having n terms it, ranging up to 2n. This would be the right summation if your array had 2n 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 2lg n. Plugging that in gives
2 · 2lg n - 1 = 2n - 1 = Θ(n)
Therefore, the total work done comes out to Θ(n), not Θ(2n).
Hope this helps!
Problem
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