4 ms·
Insertion into an array list at a uniformly-distributed location is always O(n): you can't avoid moving half the list. Appending is amortized O(1).
by ncw33 10y ago
Insertion into an array list at a uniformly-distributed location is always O(n): you can't avoid moving half the list. Appending is amortized O(1).
- rifung 10y agoNot the person you're responding to but perhaps that person meant assuming your insertions are uniformly distributed? Then I think insertion is O(n) amortized..? At an insertion you'd have (n + (n-1) + .. + 1)/n = O(n^2) / n = O(n) The first part comes from each possible run times, each with probability 1/n. You might have to expand the list but that'd also be O(n) amortized.
- deleted 10y ago[deleted]
- Kenji 10y agoYou are right, my bad. I meant appending.