1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You seem to be considering the complexity of all repeated doublings as one? But the relevant measure is the complexity of one single append of one element to the array. $\endgroup$ – Guildenstern Jun 1 '14 at 14:01
  • $\begingroup$ @Guildenstern could you explain a bit more? $\endgroup$ – Dubby Jun 1 '14 at 14:03
  • 2
    $\begingroup$ You only have to double if the array is full; when it isn't, you can simply add to the next free cell. If you initialize with say 8 empty cells, then you can do 8 appends in constant time. But when it is full, you have to double it so that takes $n$ time, where $n = 8$. But you only have to do that a few times; you do this $O(n)$ operation only every $n$th append. So instead of considering the worst case complexity, consider; what is the amortized complexity (look it up if you haven't heard of it)? $\endgroup$ – Guildenstern Jun 1 '14 at 14:05
  • $\begingroup$ I assumed that append to arrays was what you were after. Your question doesn't really make sense to me, as it is. "Repeated doubling" doesn't make sense in this context: why not just double the size of the array when you need to? Repeated doubling sounds like some batch operation. Or is it the cumulative doubling of the array over its "lifetime"? $\endgroup$ – Guildenstern Jun 1 '14 at 14:08
  • $\begingroup$ edited the question @Guildenstern $\endgroup$ – Dubby Jun 1 '14 at 14:09
7
$\begingroup$

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)$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.