Re:When Big O Fools You
by rifung on Tuesday August 23, 2016 @01:16PM
(#12345391)
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.
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.