your algorithm need O(n^2) preprocess time and so the total time is still O(n^2). I guess the author asks a really O(n lg n) time algo
On Tue, Nov 3, 2009 at 6:19 PM, anilkumarmyla <[email protected]> wrote: > I propose another solution with O(N LogN) Time Complexity and O(N^2) Space > complexity (not sure if it would count towards space or time) > > Space > 1) Generate all possible combinations of A[i] + B[j] and maintain them in an > array D (N^2 array) ---> O(N^2) > 2) Build a min or max heap out of D array using bottom up building ---> > O(N^2) > > Now D contains all possible sums of A[i] and B[j] in heap formation and the > maximum height of the heap is O( Log N^2) = O(Log N) > > Time > 1) For each C[k] search for -C[k] in the D heap. Search takes time atmost > the height of the heap ---> O(N Log N) > > Please correct me if I'm wrong. > > -- > > 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]. > 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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
