7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    Sep 21, 2016 at 22:01
  • $\begingroup$ Fun fact: 2 is provably the worst factor for growing an array-list. $\endgroup$
    – user541686
    Sep 22, 2016 at 3:06

1 Answer 1

10
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I'm not sure why you've written $\leq$ in the display: sure, it's true but we have equality there, unless I'm missing something. $\endgroup$ Sep 21, 2016 at 20:48
  • $\begingroup$ @DavidRicherby Just in cast that the sum is actually finite. But you're right, it's misleading. $\endgroup$ Sep 21, 2016 at 21:16
  • $\begingroup$ @YuvalFilmus Ah, I see. Feel free to nuke my edit if you don't think it makes things better. (Maybe it would be better to make the inequality strict, now.) $\endgroup$ Sep 21, 2016 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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