@jeevitesh yeah that may be right but it requires extra space as lot of space will be wasted...
On May 5, 1:44 pm, Jeevitesh <[email protected]> wrote: > Hi all, > > I am new to this group. > > My last post was deleted i do not know the reason behind it. > > I will explain my logic here:- > > as the range is 1 to n^2 we have a input array like input[n^2]. > We can take a auxillary array of size n^2 like aux[n^2]. > Scan the input array. > For each input input[i] increment by one corresponding aux[input[i]]. > After this just iterate through the aux array printing the index aux[i] > times. > > This way we can sort it in O(n) time. > > > > > > > > > > On Sat, May 5, 2012 at 2:02 PM, saurabh singh <[email protected]> wrote: > > After giving some thought,I think even radix sort may not be sufficient. > > Complexity of radix sort is O(k*n) where k is the number of buckets > > required to sort the given range. > > The number of buckets is proportional to the number of bits required to > > represent the *maximum number in the given range.*For our case the > > maximum number is O(n^2).Hence *the number of buckets required would be > > proportional to log(n^2) in the worst case.* > > Hence the worst case complexity for the given constraints using radix sort > > would be *O(n*(log n^2)) = O(n*logn).* > > This is no better than comparision sort.A slight optimization that we can > > make is to use a higher base which would reduce the number of buckets > > required but would add the cost of converting each number into the higher > > base. > > Somehow I am getting convinced worst case O(n) algorithm may not be > > possible.Working on the mathematical proof. > > > Saurabh Singh > > B.Tech (Computer Science) > > MNNIT > > blog:geekinessthecoolway.blogspot.com > > > On Sat, May 5, 2012 at 8:37 AM, saurabh singh <[email protected]> wrote: > > >> @cegprakash They are n numbers lying in the range 1 to n^2.Not > >> necessarily sorted. > >> eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem) > >> Saurabh Singh > >> B.Tech (Computer Science) > >> MNNIT > >> blog:geekinessthecoolway.blogspot.com > > >> On Sat, May 5, 2012 at 5:17 AM, Prakash D <[email protected]> wrote: > > >>> The range 1 to n^2 is already sorted > > >>> On Sat, May 5, 2012 at 12:17 AM, Algobiz <[email protected]> > >>> wrote: > >>> > How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? > > >>> > -- > >>> > You received this message because you are subscribed to the Google > >>> Groups > >>> > "Algorithm Geeks" group. > >>> > To view this discussion on the web visit > >>> >https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ. > >>> > 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. > > >>> -- > >>> 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. > > > -- > > 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. > > -- > *Thanks, > Jeevitesh Shekhar Singh.* -- 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.
