3

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?

Community
  • 1
  • 1
committedandroider
  • 8,711
  • 14
  • 71
  • 126

1 Answers1

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(n2) time to add n elements individually.

user253751
  • 57,427
  • 7
  • 48
  • 90
  • 1
    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? – committedandroider Feb 07 '15 at 01:50
  • @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) – user253751 Feb 07 '15 at 01:51
  • How did you tell it would take 4 times as long? – committedandroider Feb 07 '15 at 01:53
  • @committedandroider Think of it this way: each call to `insert` copies 1% of the array, on average. It's the same principle (but with different exact numbers) as if each call to `insert` copied 100% of the array. (Specifically, as the array gets bigger, each call to `insert` takes more time on average). (Obviously this comment isn't a mathematically rigorous explanation either) – user253751 Feb 07 '15 at 01:54
  • Ok that makes sense. Lets say I was at four million in the array. When I get to four million and a hundred, another re-sizing will occur, meaning 4 million elements are copied over. If you average that, that be 4000000/100 which is 40000 elements per insert, one percent of the original size. How do you get from that to 4 times as long though? I am curious. – committedandroider Feb 07 '15 at 01:59
  • 1
    @committedandroider If you make *n* twice as big, then that makes *n^2* 4 times as big. – user253751 Feb 07 '15 at 02:00
  • i get that but i don't get how you introduced n^2 in the first place. – committedandroider Feb 07 '15 at 02:02
  • @committedandroider it's a well-known result (so I didn't derive it myself). A Google search found http://stackoverflow.com/questions/19146037/efficiency-of-growing-a-dynamic-array-by-a-fixed-constant-each-time – user253751 Feb 07 '15 at 02:07
  • 2
    @committedandroider - If you want to really understand, do the math for yourself. – Stephen C Feb 07 '15 at 02:14