Hi Shiva. You are right we will be wasting a lot of memory. But still it depends like if we have lot of numbers in the range of 1, n^2 present in the input array then this trade off is not bad. The issue here is we cannot otherwise sort it in O(n) time unless and until we have extra space.
So we will have to live with it in this case as i do not think it would be possible in O(n) time otherwise. On Sat, May 5, 2012 at 2:33 PM, shiv narayan <[email protected]>wrote: > @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. > > -- 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.
