Let *E(n)* be the *expected* number of hits needed sort *'n'* *misplaced*numbers. The optimal strategy is to hold the numbers that are already in place and shuffle the remaining. Now after a shuffle assume that x numbers are still out of place. Hence we get the following recurrence.
E(n) = Sum[ ((nCx * !x)/n!) * E(x) ] x=0 ... N Where !x is the number of de-arrangements<http://en.wikipedia.org/wiki/Derangement>of x. Hope this helps. On Mon, May 9, 2011 at 9:51 PM, Rahul Singal <[email protected]>wrote: > abhijith can you explain , how you got E(n) = N , > > Thanks in advance > > Rahul Singal > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" 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/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" 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/algogeeks?hl=en.
