@pitush: pls explain your logic once ........
On Fri, Sep 2, 2011 at 4:09 PM, Piyush Grover <[email protected]>wrote:
> 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.
>
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
*
Mobile +91 8056127652*
<[email protected]>
--
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.
