for #2: Just create a hashtable Number-> Counts. Make one iteration through the whole List and make hashtable(Number)=hashtable(Number)+1. No comparisons so far. Then if size(hashtable)<n/2 go through each element of the hashtable and compare it with (n/2+1).
So exactly maximum n/2+1 comparisons. The complexity is O(n) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
