Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

8
  • 5
    It's a little off-topic, but I would hate for someone to get confused and not really notice the emphasis on get operations. Commented Feb 2, 2010 at 8:19
  • In the JDK code I'm looking at (1.6.0_17) the new capacity is actually calculated as (oldCapacity * 3)/2 + 1. Commented Feb 2, 2010 at 9:01
  • 1
    Quibble about the first sentence, which seems to imply that write operations run in O(n) time. That's not what the doc says, it says that adding n elements requires O(n). For individual elements, insertion time is still O(1). The re-allocation, copy etc. just make it a somewhat "bigger" O(1). Commented Feb 2, 2010 at 10:28
  • You can avoid the expansion steps if you tell the constructor how big it should be from the beginning. (if you know) Commented Feb 2, 2010 at 10:48
  • 3
    @AKh, yeah, which is why it says amortized constant time. Most insertions will be O(1), but every now and then they will be O(n). Taken as a whole, insertions will behave as O(1). Commented Sep 25, 2012 at 14:41