Greetings! The strategy should be to process the elements in pairs - and compare the larger element with current maximum, and smaller element with current minimum.
loop runs upto n in steps of 2, and in each iteration, there are 3 comparisons: - between (i)th and (i+1)th element - between min(i, i+1) and current_min - between max(i, i+1) and current_max That gives 3n/2 comparisons. Instead of doing 2 comparisons for every element (with min and max), now you're doing 3 comparisons for every pair - which makes it effectively 1.5 comparisons for each element. That's how the n/2 comparisons are saved. I hope the idea is clear. On Sun, Dec 4, 2011 at 11:32 AM, Anika Jain <[email protected]> wrote: > refer algorithms by cormen for this > > > On Mon, Nov 28, 2011 at 9:56 PM, Nitin Garg <[email protected]>wrote: > >> Find the min and max in an array. Now do it in less than 2n comparisons. >> (they were looking for the solution that finds both max and min in about >> 3/2 n comparisons). >> >> >> -- >> Nitin Garg >> >> "Personality can open doors, but only Character can keep them open" >> >> -- >> 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. >> > > > > -- > Regards > Anika Jain > > -- > 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. > -- Best Regards, Deepak -- 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.
