if I have understood the question correctly then:
a[n-1] + b[i] > a[j] + b[i] for all 0 <= j < n-1
and a[j] + b[n-1] > a[j] + b[i] for all 0 <= i < n-1
therefore,
i = j =n-1;
count = 1;
S[0] <-- (a[n-1], b[n-1])
p = a[n-1] + b[n-2];
q = a[n-2] + b[n-1]
while(count < n){
if(p > q){
j--;
S[count++] <-- (a[n-1], b[j]);
}else{
i--;
S[count++] <-- (a[i], b[n-1]);
}
p = a[n-1] + b[j-1];
q = a[i-1] + b[n-1];
}
Time complexity: O(n) : http://ideone.com/FXfVj
On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank <[email protected]>wrote:
> @Dave Correct , Missed to Provide the Correct Time Complexity in Worst Case
> it Will be O(N^2) , as we need to find out n such maximum pair , will think
> about O(N0) Algo, if able to do it, will post the Algo here
>
> Thanks
> Shashank Mani
> Computer Science
> Birla Institute of Technology,Mesra
>
> --
> 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/-/a14Pj22tbJgJ.
>
> 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?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].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
