Algorithm Analysis Problems #9) Please explain the solution thoroughly it\'s mor

Question

Algorithm Analysis Problems #9)

Please explain the solution thoroughly it's more important than the answer itself. Here is my class work and a provided link to origonal word document. Thank You.

https://docs.google.com/document/d/1sgmQ24EZxDZL7WfqPh_hjz2MNu2wGGvl47rQrmFeagY/edit?usp=sharing

9. (10 pts) 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? C. in class befon? ok o Compute median on smallest Confin each element with the me ordering the element is larger it in the first se- smell large h in Second Set

Explanation / Answer

The algoruthm stated above is correct. To summarize, the steps would be

1. Compute the median, say M

2. Compare each element in the list with M

3. If the element is smaller than M, put it in set 1

4. If the element is larger than M, put it in set 2.

The algorithm to find median takes O(n) time. Comparing n elements of the array one by one with the median (steps 2,3 & 4) takes 'n' time. So,

T(n) = O(n) + n

= O(n)

The minimum time complexity of the algorithm is O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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