[Solved]: Amortized time cost of insertion into an Array list

Problem Detail: 

A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied over into the newly resized array 1, 2, 4, ... , n number of copies. What then is the sum of this sequence? To answer that we see that the sequence written backwards is n + n/2 + n/4 + ... + 1. Until here I understand what has been said. Here is where my confusion starts, how is this sequence roughly equal to 2n? How do we know this? Once we settle that we can say that n insertions take O(2n) time, but from that how do we deduce that the amortized time for each insertion is O(1).

Asked By : Anonymous Human

Answered By : Yuval Filmus

For the estimate, $$ n + \frac{n}{2} + \frac{n}{4} + \cdots +1 <n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n, $$ since $1 + 1/2 + 1/4 + \cdots = 2$.

If $n$ insertions take $O(n)$ time, then the amortized time per insertion is $O(n)/n = O(1)$. This is by the definition of amortized time. (More accurately, the amortized time is at most $K$ if $n$ insertions take at most $Kn$ time, for every $n$.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63752

3.2K people like this

 Download Related Notes/Documents