Suppose you are choosing between the following three algorithms, all of which ha

Question

Suppose you are choosing between the following three algorithms, all of which have 0(1) base cases for size 1: 1. Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time. 2. Algorithm B solves problems of size n by recursively solving one subproblem of size n/2, one subproblem of size 2n/3, and one subproblem of size 3n/4 and then combining the solutions in linear time. 3. Algorithm C solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in 0(n^2) time. What are the running times of each of these algorithms (in asymptotic notation) and which would you choose? You may use the Master Method. Hint: Approach Algorithm B via the substitution method. Formatted - pastebin. com/WqjWFtbM

Explanation / Answer

SOLUTION: A T(n) = 5 * T( n/2 ) + O(n) a = 5; b = 2; d = 1 (from general form) d 1 2 = log 9 b 3 2 so O( n log n ) ALGORITHM C is the best of the three

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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