Consider the case
n=6
array elements :-
{36 36 36 36 36 36}
How many iterations your code makes?
Consider another case
n=1000000
array={1e12,1e12 ......repeated 10^6 times}
How many iterations your code make?
Are the iterations still proportional to n that is the number of elements
in the array?
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.comOn Sat, May 5, 2012 at 2:14 PM, Jeevitesh <jeeviteshshekha...@gmail.com>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 <saurab...@gmail.com> 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 <saurab...@gmail.com>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 <cegprak...@gmail.com> wrote: >>> >>>> The range 1 to n^2 is already sorted >>>> >>>> On Sat, May 5, 2012 at 12:17 AM, Algobiz <deepak.arulkan...@gmail.com> >>>> 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 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. >>>> >>>> -- >>>> 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. >>>> >>>> >>> >> -- >> 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. >> > > > > -- > *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 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. > -- 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.
