LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 06-09-2006, 01:09 AM   #1
George2
Member
 
Registered: Oct 2003
Posts: 354

Rep: Reputation: 30
[interesting question] find an element which is sum of two other elements


--------------------------------------------------------------------------------

Hello everyone,


I am discussing with my friends about an interesting question about find the maximum element in a set, which is the sum of two other elements.

For example, in set {1, 2, 3, 5, 8, 10}, the answer is 10 (10 = 8 + 2),
which is the maximum element we can find, and it is the sum of two
other elements (8 and 2) in the set.

Currently, I only have brute-force solution. Sorting the set, which takes O(nlgn) time, then enumerate them one by one to find whether two elements can sum up to the maximum element (if the most maximum element does not meet the condition, move to the second largest one), which takes O(n^2) time, so the total time complexity is O(n^2).

I am wondering whether any one have better ideas?


thanks in advance,
George

Last edited by George2; 06-09-2006 at 01:43 AM.
 
Old 06-09-2006, 01:57 AM   #2
elyk1212
Member
 
Registered: Jan 2005
Location: Chandler, AZ USA
Distribution: Mandrake/Mandriva 10.2
Posts: 186

Rep: Reputation: 30
I don't know for sure, but my idea would be to have a set with all permutated results (all possible add combinations) and keep this for your checks. Not sure if that would help, really.

This is probability Combinations.. so....
BigTheta( N!/(N-R)!) ?

Depends on how large N is...? In this case, 6!/(6-2)! => 6*5 = 30. So the other case was O(N^2) = 6^2 = 36, thus I think it saves some time on the check, in this example. But it could become larger as more checks are necissary. You will need to iterate through all combos found for each max found. Sort of a O(NM). Where M = BigTheta( N!/(N-R)!).

Last edited by elyk1212; 06-09-2006 at 02:44 AM.
 
Old 06-09-2006, 06:07 AM   #3
graemef
Senior Member
 
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
I believe that the formula gave was for permutations and as you said you only need combinations, so your Big Oh would be (N!/(N-R)!R!) for R = 2 that will give you N(N-1)/2 which is significantly better than N^2, although the Big Oh will be the same.

But I agree with the approach of sort the original list, calculate the combinations, compare.
 
Old 06-09-2006, 12:48 PM   #4
elyk1212
Member
 
Registered: Jan 2005
Location: Chandler, AZ USA
Distribution: Mandrake/Mandriva 10.2
Posts: 186

Rep: Reputation: 30
You are right. Should be: N!/[(N-R)!R!].

But that should be BigTheta, I think, as that is the asymptotic lower, and upper bound. There is no worst or best case of combination variance, there only is X number of combos, which will not change (N held constant). So f(C) will always take C!/[(C-2)!2!], best and worst case.

Not that it matters, really.

Last edited by elyk1212; 06-09-2006 at 12:55 PM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
"The volume control did not find any elements and/or devices to controll" Redeyes_Gambit Linux - Software 1 11-26-2005 06:04 PM
point / STL vector, change element question true_atlantis Programming 1 09-17-2005 01:46 PM
XML question multiple parents for child element pld Programming 1 03-17-2005 02:14 PM
arrays of elements with [gcc4]array type has incomplete element type lmmix Linux - Software 0 02-26-2005 08:07 AM
One interesting question palanisaravanan Linux - Networking 2 04-21-2004 09:39 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 10:07 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration