When Big O Fools You

Re:When Big O Fools You by ncw33 on Tuesday August 23, 2016 @12:47PM (#12345134)

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

[ Parent | on HN ]

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.

[ Parent | on HN ]

Re:When Big O Fools You by Kenji on Tuesday August 23, 2016 @02:16PM (#12346042)

You are right, my bad. I meant appending.

[ Parent | on HN ]