@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 <[email protected]> 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 <[email protected]> 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 > > <[email protected]>wrote: > > >> @dufus.. > >> if there is constant space requirement then ?? > >> wat will be your soln ?? > > >> On Sat, Sep 5, 2009 at 12:35 PM, Dufus <[email protected]> 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> > > >>> Then using it we can find the kth smallest element in O(nk) time. > > >>> _dufus > > >>> On Sep 4, 10:03 pm, ankur aggarwal <[email protected]> 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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
