If you have n-element cycle, P(1) = probability to get it sorted in 1 shot = 1/n P(2) = probability to get it in 2 shots = probability to not get it in 1st shot * probability to get it in 2nd shot = (n-1)/n . 1/n P(3) = [(n-1)/n].[(n-1)/n].1/n and so on
Expected value of n = E(n) = 1.P(1) + 2.P(2) + 3.P(3) + ... inf terms If you write down this sequence, you will notice that this is an arithmetical geometric sequence. Solve it and you get E(n) = n. On further analysis, you will find that the solution is as simple as the number of elements not in place. On 8 May 2011 07:22, Balajiganapathi <[email protected]> wrote: > I meant: Is n the expected number of hits to sort a n-element *cycle*. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
