I understand it's constant to add to an empty array, but after the first element is added, doesn't the time shift to O(N)?
Similarly, does removing a single element from the middle of the array change the whole indexing of the array of just the left side (from n/2 to n )?
Adding to an Array often means allocating a new array of size n+1 and copying all the content. This takes O(N) time, if the array is empty (or in fact any fixed size, but practically any small size) you can call this O(1).
What most collection libraries do is provide a growable array like collection which is actually an Array and an extra integer size counter. When the underlying array is filled to capacity and we want to add another element we don't grow it by 1 but by some multiplicative factor(e.g 2, doubling it's size). This is done as above, allocating a larger array and copying content, preferably using page level efficient copying for larger arrays. This gives amortaized O(1) time for adding an element, but worst case O(N). N being the number of elements in the array.
If you remove an element from the middle of an array you may refer to an operation which shifts all data past that index back by one, or you might be refering to an operation which just sets that index to null or other empty value. The first is O(N) the second is O(1)
Array? or arrays in general?