Not 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..

Not 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.