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

Question

Suppose you are choosing between the following three algorithms:
a. Algorithm A solves problems by dividing them into five subproblems of half the size, solving each subproblem, and then combining the solutions in linear time.
b. Algorithm B solves problems of size n by recursively solving one subproblem of size n-1 and then combining the solutions in constant time.
c. 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 O(n2) time.
What are the running times of each of these algorithms (big-O notation), and which would you choose?

Explanation / Answer

Algorithm A: Running time T(n) = 5T(n/2)+ O(n) = O(n^log25)

Algorithm B: Running time T(n) = 2T(n-1) + O(1) = O(2n).

Algorithm C: Running time T(n) = 9T(n/3)+ O(n2) = O(n2 log n).

Of these, Algorithm C is the fastest.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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