A correction in the proposed algorithm.
On Tue, Sep 15, 2009 at 1:08 PM, Shishir Mittal <[email protected]>wrote:
>
>
> *Algorithm.*
> 1) Corresponding to each element in X, create a node with 2 values, to be
> compared indexed of Y, and the corresponding sum.
> NODE[i] = {yIndex, sum = X[i] + Y[yIndex]}
*Corresponding to each element in X, create a node with 3 values, xIndex,
corresponding yIndex, and the corresponding sum.
NODE[i] = {xIndex = i, yIndex=0, sum = X[xIndex] + Y[yIndex]}*
>
> 2) Form a MinHeap of the nodes.
> 3) Increment the yIndex of the root node of heap and also the corresponding
> sum value.
> 4) Min Heapify this array of nodes, with key as sum value.
> 5) Repeat steps 3 and 4, k-2 times.
> 6) sum value of root node is the required answer.
>
> Space Complexity : O(n),
> Time Complexity : O(n + (k-1)logn).
>
> For k = n, Time complexity : O(nlogn).
>
>
> --
> Shishir Mittal
> Ph: +91 9936 180 121
>
--
Shishir Mittal
Ph: +91 9936 180 121
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
