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 subproblems of half the size, recursively solving each subproblem, and then 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 n by dividing them into nine subproblems of size nf 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.