Spotted a mistake in my approach. Heaps are not good for searching purpose [:|] Can anybody shed light on building Red-Black trees from a random array and the search time for an element ?
On Tue, Nov 3, 2009 at 3:49 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.
