@DK sir I was just assuming n^2 values as the 2D matrix......not creating although i am using a O(n^2) space that keep track of which cell is already in heap and need not be inserted again........so initially all the need to be initialized......that will make it O(n^2)
Now I have a Doubt - Is there any way i can initialize this space so that overall complexity is O(nlgn) like making this space static or global (so all memory will be initialized to zero) or using memset is that still O(n^2) ?? On Mon, Jul 11, 2011 at 12:34 AM, DK <divyekap...@gmail.com> wrote: > Largest value is of course A(n) + B(n). > Second largest value is either A(n) + B(n-1) or A(n-1) + B(n). > > Select the largest among both and continue down that array. > Maintain 2 pairs: > Pair 1: Hold first value constant, go down the second array. Pair 2: Hold > 2nd value const. and go down the first array. > Whenever one element of a pair cannot find a partner, that implies that all > pairs containing that element have been considered. > Discard that partner-less element and continue down the array. Take special > care that duplicate elements are not output. See the output below so that > things are clearer. (The duplicates case arises when the pair chosen in both > cases is the same). > > eg. > > 1 7 9 > 2 3 4 > > > Pair 1: (9,4) Pair 2: (9,4) -> Output (9,4) = 13 > Pair 1: (9, 3) Pair 2: (7,4) -> Output (9,3) = 12 > Pair 1: (9, 2) Pair 2: (7,4) -> Output (7,4) or (9,2) -- assume (9,2) was > output = 11 > Pair 1: (7,4) Pair 2: (7,4) -> Ouput (7,4) = 11 > Pair 1: (7,3) Pair 2: (1, 4) -> Output (7, 3) = 10 > Pair 1: (7,2) Pair 2: (1,4) -> Output (7,2) = 9 > Pair 1: (1,4) Pair 2: (1,4) -> Output (1,4) = 5 > Pair 1: (1,3) Pair 2: (1,3) -> Output (1,3) = 4 > Pair 1: (1,2) Pair 2: (1,2) -> Output (1,2) = 3 > Pair 1: (empty) Pair 2: (empty) -> End > > O(N) algorithm. Descending order printing of pairs. > > @Sunny: Your time complexity is O(N^2) as creating that array will take > O(N^2) time. > @Dumanshu: Your algorithm misses cases. Eg. (9,4) will be printed but (9,3) > will not. > > -- > DK > > http://twitter.com/divyekapoor > http://www.divye.in > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/uJEiQKMYJnMJ. > > 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?hl=en. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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?hl=en.
