+1 siddarth On Sat, Sep 3, 2011 at 2:54 PM, Dheeraj Sharma <dheerajsharma1...@gmail.com>wrote:
> yeah..we it works for +ve number..within some specified range..it was > alternate to O(nlogn) solution..if range is known > > > On Sun, Sep 4, 2011 at 12:07 AM, mohit verma <mohit89m...@gmail.com>wrote: > >> @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. >> > > > > -- > *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. > -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers <=> Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> * Mobile +91 8056127652* <bagana.bharatku...@gmail.com> -- 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.
