fuck you guys you do this and don't find out where the 10k topic is.

just realized i was on the wrong account. the only thing i have to add is QED.

I think that the necessary number of bumps would be the cumulative number of positions that a post has been promoted for the post that has the greatest such number. Call this number q. It would take q bumps of other posts to force this post back to its proper position. But would q bumps be sufficient? No, unless the post that qualifies for q has just been bumped. Suppose that the post that qualifies for q is currently in position p. It would have to be bumped to first before other posts could be bumped in front of it, so it will have been promoted an additional p-1 places, so p+q-1 bumps would be needed.

skrum your formula only gets one post back into place i believe.

nm our formulas say the same thing just in different terms

10071

"the cumulative number of positions that a post has been promoted for the post that has the greatest such number"
???

monte is right (and I said the same thing basically). the worst case scenario is completely reversed order. it would then take 1 bump for every post to to the beginning, so you would have to do this for all but the last post, hence n-1. detenmile basically said that you could subtract 1 for every post that was already in the correct order, which is correct.

O(n) denotes that as as the # of posts grows, the amount of bumps needed grows at the same rate (as opposed to exponentially, logarithmically, etc.)

My analysis was incomplete. I was speaking of q as if there was only one post that had the maximum q. If there are strings of posts in the correct order, their values of q would be the same.

I am trying to expand the analysis to get a more general result than just the worst case.

It's n - the length of the longest increasing (not necessarily contiguous) subsequence.

length of the longest increasing (not necessarily contiguous) subsequence must start with the post that is to be the oldest post though. If not then you have to bump posts until the oldest post is in it's proper position. Your bump order would be (obviously) 2nd oldest post, 3rd oldest, 4th oldest,.......newest.