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 <[email protected]> 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 < > [email protected]> wrote: > >> count sort in reverse order would help i guess :) >> >> >> On Sat, Sep 3, 2011 at 11:49 PM, mohit verma <[email protected]>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 <[email protected]>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 < >>>> [email protected]> 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 [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. >>>>> >>>> >>>> >>>> >>>> -- >>>> ........................ >>>> *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 [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. >>> >> >> >> >> -- >> *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 [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. >> > > > > -- > ........................ > *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 [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. > -- *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 [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.
