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 into four subproblems of half the size, recursively solving each subproblem, and thon combining the solutions in linear time. Algorithm B solves problems of size n by recursively solving two subproblems of size n - 1 and then combining the solutions in constant time. Algorithm C solves problems of size by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n2) time. What are the running times of each of these algorithms (in big-O notation), and which would you choose?

Explanation / Answer

a) T(n) = 5T(n/2) + O(n) =O(nlog5/log2) = O(n2.32)

b) T(n) = T(n-1) + O(1) = O(n)

c) T(n) = 9T(n/3) + O(n2) = O(n2 logn)

B will be the best choice because of its least complexity.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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