Problem Detail: 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? 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
Asked By : Dubby
Answered By : David Richerby
Both are correct but you’re using $n$ to mean two different things:
- when you say that $1 + 2^1 + 2^2 + dots + 2^n = (2^{(n-1)} – 1) sim O(2^n)$, you’re using $n$ to mean the number of times you had to increase the size of the array;
- when you say that $1 + 2 + 4 + dots + n/4 + n/2 + n sim O(n)$, you’re using $n$ to mean the total size of the array after you’ve extended it some number of times.
So, you should never just say “$n$”, without saying what it means. Normally, $n$ refers to the size of the input to a problem. In this case, that would probably be the number of things you want to insert into the array. This is closest in meaning to the second case above since, when you’ve inserted $n$ elements, the total size of the array will be somewhere between $n$ and $2(n-1)$ (i.e., it will be $O(n)$).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/26296
