In the Swift Apprentice v.2 book, towards the end of Chapter 8: Arrays, it talks about the performance (using Big-O notation) of array manipulations.
I get that if you want to insert an element in the middle of the array, it needs to move elements around to make room for the new element.
I am also guessing that mutable arrays in Swift works similarly to NSMutableArrays in Objective-C in that the array reserves some space at the end for new elements, and only need to copy itself to a bigger space if the first space is full.
But how can inserting an element at the beginning of the array be O(1)? Doesn’t the array need to be copied over with that new element in the first spot?
For example, let say we have
let players = ["Bob", "Cindy", "Dan", "Eli", "Frank"]
We’re missing Alice, so we do:
players.insert("Alice", at: 0)
I would assume it needs to copy Alice + players altogether in a new location in memory, effectively copying the first array, which would give us O(N) in performance.
The same question applies to deleting an element at index 0.
Thank you!