S0#9 | Algorithm Analysis | Discrete Math | Big 0 Notation 9. Consider the follo

Question

S0#9 | Algorithm Analysis | Discrete Math | Big 0 Notation

9. Consider the following problem. Given a list of n (n even) distinct positive integers, partition the list into two sub-lists of size n/2 such that the difference between the sums of the integers in the two sub-lists is maximized. Give an algorithm of lowest O complexity for solving the above problem. State your algorithm in no more than four simple English sentences. Do not write a pseudocode. What is the O complexity of your algorithm?

Explanation / Answer

we will assume a list of some positive disctinct even integers

let the lists be

*list:2,2,4,8,16,6,,2,10,20,4

now split this list into two sub lists of size n/2 i;e; divide the above lists into two equal parts having equal number of integers

*sub list 1:2,2,4,16,10

*sub list 2 :8,6,2,20,4

now we will calculate the sum of each sub lists

*sum of sublist 1 is 34

sum of sub list 2 is 40

now calculate the differenc of the sum of integers

*difference od sub 1 and sub 2 is 6

but according to the question we have to find differenceof sums of sublists whic is maximized.

so now lets split the list into

sublist1=2,2,2,4,4

sublist2: 8,16,6,10,20

now

sum of sub list 1:14

sum of sub list 2 is :60

now difference is 46

we can see that this result is greater than the previous one,and also this is the maximum for the assumed list.

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

according to this algorithmwe can state that, weneed to divide a list into two equal part,one with all lowest numbers and other with the bigger ones,and then have to find the difference to get the maximum difference.

-----------

time complexity for this algo is

2n+n=2*10+2=22

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.