@dheeraj - for count sort we need to know the range the numbers are in. Otherwise how will u initialize array keeping count?
On Sun, Sep 4, 2011 at 12:03 AM, Dheeraj Sharma <dheerajsharma1...@gmail.com > wrote: > count sort in reverse order would help i guess :) > > > On Sat, Sep 3, 2011 at 11:49 PM, mohit verma <mohit89m...@gmail.com>wrote: > >> Ohh my bad. the complexity should be >> O(nlogn) + O(mlogm) +O(m) = O(tlogt) where t=max(m,n) >> >> >> On Sat, Sep 3, 2011 at 11:46 PM, mohit verma <mohit89m...@gmail.com>wrote: >> >>> create a binary search tree by scanning the whole array and if the value >>> already exists increase count field in that node O(nlogn). Now traverse the >>> tree in any order by creating another tree with kery - count. O(nlogn). >>> Doing reverse inorder traversal print value field of each node count number >>> of times O(n). >>> >>> overall complexity - O(nlogn)+O(nlogn)+O(n) = O(nlogn). >>> >>> >>> On Sat, Sep 3, 2011 at 11:16 PM, Siddhartha Banerjee < >>> thefourrup...@gmail.com> wrote: >>> >>>> perhaps we can make it O(mlogm), m= no of distinct elements... just >>>> create a hash table and store the count of the number of time elements >>>> occur... O(n), now sort the m elements and proceed as above... >>>> it is obviously not possible to do it faster than O(mlogm), where m = no >>>> of distinct elements... >>>> so order = O(n+mlogm)=O(mlogm)(???, assuming m!<<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 >>>> algogeeks+unsubscr...@googlegroups.com. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> ........................ >>> *MOHIT VERMA* >>> >>> >> >> >> -- >> ........................ >> *MOHIT VERMA* >> >> -- >> 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 >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > *Dheeraj Sharma* > Comp Engg. > NIT Kurukshetra > +91 8950264227 > > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- ........................ *MOHIT VERMA* -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
