More appropriate to say Amortized O(1) vs O(n) for insertion into unsorted dynamic array?

Question

This falls under "a software algorithm" from stackoverflow.com/help/on-topic, in this case, a software algorithm to add an item to a dynamic unsorted array

This is chart we made in class about the runtimes of operations on different data structures enter image description here

The question I have is about the runtime for inserting(or adding) a value into the dynamic unsorted array. Here is our code for doing this

 public void insert(E value) {
    ensureCapacity(size + 1);
    elementData[size] = value;
    size++;
}
  private void ensureCapacity(int capacity) {
    if (capacity > elementData.length) {
        int newCapacity = elementData.length + 100;
        if (capacity > newCapacity) {
            newCapacity = capacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

I understand how this could be interpreted as O(n). The ensureCapacity function is technically apart of the operations that consist of insert and then with runtime analysis, https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html, you would say that the worst case of the two branches is when every element of the original array is copied into the new array which is an O(n) operation. So the worst case or big oh of the whole function is O(n)

Could an argument be made for amortized O(1) time as well(What is amortized analysis of algorithms?) because each time you resize, you have to wait a specific amount of time before the next resize?

In that chart, would O(1) also make sense then?

Stack Exchange Broke The Law · Accepted Answer · 2015-02-07 01:39:29Z

8

No.

"Amortized O(1) time" means a very specific thing - it means that the cost of inserting n items, one at a time, is O(n). It is not enough to say that "the things that take a long time don't happen very often" - you do actually have to analyze the algorithm mathematically.

This particular case (inserting an item into an array, or resizing it if full) is a well-known one. As it turns out, if you resize the array by a constant factor (e.g. doubling it each time it's full) then this operation is amortized O(1). If you add a fixed number of elements (e.g. adding 100 each time it's full) then it's still amortized O(n), because it takes O(n²) time to add n elements individually.

answered Feb 7, 2015 at 1:39

Stack Exchange Broke The Law

59.2k7 gold badges57 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

committedandroider Over a year ago

What do you mean when you say "it takes O(n^2) time to add n elements individually". Shouldn't that just be O(n) cause you're just moving the elements from the old array into the new one?

Stack Exchange Broke The Law Over a year ago

@committedandroider If you make a new dynamic array (using your code), and add 50,000,000 elements, it will take about 4 times as long as if you added only 25,000,000 elements. (Obviously the actual definitions of O(n) and O(n^2) don't use the word "about", but this is close enough)

committedandroider Over a year ago

How did you tell it would take 4 times as long?

Stack Exchange Broke The Law Over a year ago

@committedandroider If you make n twice as big, then that makes n^2 4 times as big.

Stephen C Over a year ago

@committedandroider - If you want to really understand, do the math for yourself.

|

Collectives™ on Stack Overflow

More appropriate to say Amortized O(1) vs O(n) for insertion into unsorted dynamic array?

1 Answer 1

9 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Linked

Related