Suppose you are choosing between the following three algorithms: Algorithm A sol

Question

Suppose you are choosing between the following three algorithms: Algorithm A solves problems by dividing them into five sub problems of half the size, recursively solving each sub problem, and then combining the solutions in linear time. Algorithm B solves problems of size n by recursively solving two sub problems of size n 1 and then combining the solutions in constant time. Algorithm C solves problems of size n by dividing them into nine sub problems of size n/3, recursively solving each sub problem, and then combining the solutions in theta(n^2) time. Which would you choose? Explain.

Explanation / Answer

We do not pick algorithm 3 as it takes too long to combine the solution.

Splitting into 2 subproblems takes less time than 5 sub problems since the combining is constant for both. Thus algorithm A.

Although this is greatly dependent on the side of data, splitting time and recombining time.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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