Finding the range(min & max) of an array takes O(n). So that is not an issue. But if the array is sparse i.e. very few elements in a large range, then this method would not be effective considering space utilization.
-Abhirup On Mon, Jun 28, 2010 at 2:28 PM, Abhishek Sharma <jkabhishe...@gmail.com> wrote: > may be to figure out the range while reading the numbers or taking the mos > as input... we can have two variables (min and max) that contains the > minimum and maximum elements encountered so far respectively... > i.e. whenever we read a no n we compare it with min and max... > if n<min then min =n > or if n>max then max = n; > > so the range would lie between min and max.. > > correct me if I am wrong.. > > On Mon, Jun 28, 2010 at 2:20 PM, nisha goyal <nisha.goyal1...@gmail.com> > wrote: >> >> @abhirup: range is required in counting sort.... how can you decide that?? >> please elaborate.... >> >> On Mon, Jun 28, 2010 at 12:01 PM, Abhirup Ghosh <abhiru...@gmail.com> >> wrote: >>> >>> We can sort the array in O(n) time using counting sort. And then take >>> the difference of consecutive elements in O(n) time to get the minimum >>> one. >>> >>> -Abhirup >>> >>> >>> >>> On Mon, Jun 28, 2010 at 10:36 AM, Jagadish M <jagadis...@gmail.com> >>> wrote: >>> > In the general case, we can reduce Element-Distinctness(ED) problem to >>> > this problem. Since ED has a lower bound of Omega(n log n), we cannot >>> > get an O(n) algorithm for this problem. >>> > >>> > http://en.wikipedia.org/wiki/Element_distinctness_problem >>> > >>> > >>> > -Jagadish >>> > http://www.cse.iitb.ac.in/~jagadish >>> > >>> > >>> > >>> > On Jun 27, 5:55 pm, sharad kumar <sharad20073...@gmail.com> wrote: >>> >> How to find the two numbers whose difference is minimum among the set >>> >> of >>> >> numbers >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> > Groups "Algorithm Geeks" group. >>> > To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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 algoge...@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.
