Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer?

Question

I had trouble formatting the summation symbols, so if anyone knows how to do it correctly feel free to edit.

I just read the asymptomatic analysis chapter from CLRS. While the aggregation and potential method are clear to me, I thought I should do some extra practice with the accounting method. My goal was to prove that if you have an array size 1, and when it fills up, you double the size, results in a time complexity of O(1) per operation. Using aggregate analysis, here is the proof I came up with:

If you call append n times, then the time complexity would be this:

$\sum_{i=1}^{\log n} \frac{1}{2^i}$

which is less than

$\sum_{i=1}^{+\infty} \frac{1}{2^i}$

which is equal to 2ドルn$. So, the time complexity for all N operations will be O(N), so the time complexity for a single operation is O(1).

However, if the size starts at 1, then adds by 1 instead of multiplying by 2 (meaning, size starts 1, then becomes 2, then becomes 3, etc...) then the time complexity should be O(N), which I get using aggregate analysis. $\sum_{i=1}^{n} (i+1)$

the extra 1 comes from actually placing the next element. This is equal to around (n(n + 2)) / 2, or O(N ^ 2) for all N operations, and O(N) for a single operation, which is correct. However, using the accounting method I get another answer. The actual cost of placing an element is 1, and the asymptomatic cost I set is 2. So the first time costs 2, and the second call the copying doesn't take any extra time because I prepaid it before, and the extra cost of placing that element is 2. So, it becomes:

$\sum_{i=1}^{n} 2$

which is equal to O(N) for all total operations, and O(1) for a single operation. This isn't the correct output. Where did I go wrong, and how can I fix it?

Answer 1

First of all notice that your first aggregate analysis should read $\sum_{i=1}^{\log n} 2^i = 2^{\log n + 1} - 2 < 2n$. (What you have written makes no sense since $\sum_{i=1}^\infty \frac{1}{2^i} \le 1$, which would mean that the aggregate complexity is upper bounded by a constant regardless of the number of operations).

Then in your last analysis you can't just place one extra credit on each element because it would only pay for the first time that such element is copied (i.e., only for the next insertion).

• nishantc1527: This was very helpful, thanks a lot. I'm very new to this summation stuff since I'm only in 6th grade, however after reading a few identities, I think I have a better understanding.