Java – more appropriately, amortized o (1) vs o (n) for inserting unordered dynamic arrays?

This belongs to stackoverflow COM / help / on topic's "software algorithm", in this case, is a software algorithm that adds items to a dynamic unordered array

This is a chart of the operation run time on different data structures in class

My question is about the runtime that inserts (or adds) values into dynamic unordered arrays This is the code we use to do 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 that this can be interpreted as O (n) The ensueacapacity function is technically the difference between operations consisting of insert and runtime analysis, https://academics.tjhsst.edu/compsci/CS2C/U2/bigoh.html , you would say that the worst case of two branches is the (n) operation when each element of the original array is copied into the new array So the worst case or big case of the whole function is O (n)

What is amortised analysis of algorithms Debate because each time you resize, do you have to wait a specific period of time before the next resize?

In that chart, will o (1) also make sense?

Solution

No,

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

This special case (inserting items into an array, or resizing if full) is well known It turns out that if you adjust the size of an array by a constant factor (for example, double it whenever it is full), then this operation is amortization o (1) If you add a fixed number of elements (for example, add 100 each time you fill up), it is still apportioned o (n), because it takes O (N2) time to add n elements alone