@mittal I am not able to understand ..... How are you updating the C array?......You didnt tell what will be the updated array after second element?....Please elaborate...
On Wed, Sep 16, 2009 at 9:21 PM, Dufus <rahul.dev.si...@gmail.com> wrote: > > @Anil > Thats right O(n,n) time complexity for k=O(n). > Still it is better than Rama's O(n*m*log k) > which would be order O(n.n.logn) in worst case. > > // sorry for the delay in response. I was away for a week with no > access to internet > _dufus > > > On Sep 15, 11:19 am, Anil C R <cr.a...@gmail.com> wrote: > > @dufus > > if extracting the kth smallest element would tske O(kn) then extracing > the > > nth element would take O(n^2) right? > > > > On 9/14/09, Ramaswamy R <ramaswam...@gmail.com> wrote: > > > > > > > > > I am not sure if constant space requirement is possible. But we can do > it > > > with O(k) space complexity. > > > > > Maintain a max heap of k elements. For each of the n*m sums add it to > the > > > heap (if it ain't full with k elements) or replace the root and heapify > if > > > the sum is lesser than the root. > > > > > Finally the root will have the k'th smallest sum. > > > > > But this would require O(n*m*log k) time complexity. > > > > > On Sat, Sep 5, 2009 at 5:10 AM, ankur aggarwal < > ankur.mast....@gmail.com>wrote: > > > > >> @dufus.. > > >> if there is constant space requirement then ?? > > >> wat will be your soln ?? > > > > >> On Sat, Sep 5, 2009 at 12:35 PM, Dufus <rahul.dev.si...@gmail.com> > wrote: > > > > >>> It seems EXTRACT_MIN for Z[n^2] can be done in O(n) time. > > >>>http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf<http://lyle.smu.edu/%7Esaad/courses/cse3358/ps5/problemset5sol.pdf> > <http://lyle.smu.edu/%7Esaad/courses/cse3358/ps5/problemset5sol.pdf> > > > > >>> Then using it we can find the kth smallest element in O(nk) time. > > > > >>> _dufus > > > > >>> On Sep 4, 10:03 pm, ankur aggarwal <ankur.mast....@gmail.com> wrote: > > >>> > Find nth smallest inO(n) Given two arrays of length n in sorted > order > > >>> > X[n] & Y[n]. > > >>> > Now make another array Z[n^2]={such that z belongs to X+Y}. > > >>> > AS all possible sum of x+y is there in Z. You have to give the nth > > >>> smallest > > >>> > no of Z in O(n) time. > > >>> > Space complexity : No bound on it. But try to optimize it if > possible. > > > > > -- > > > Yesterday is History. > > > Tomorrow is a Mystery. > > > Today is a Gift! That is why it is called the Present :). > > > > >http://sites.google.com/site/ramaswamyr > > > > -- Mangal Dev B.Tech. Part-IV, Department Of Computer Science & Engineering, Institute Of Technology, BHU --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
