Suppose you are choosing between the following three algorithms to solve a probl

Question

Suppose you are choosing between the following three algorithms to solve a problem: . Algorithm A solves the problem of size n by dividing them into five subproblems of size n/2, conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in time linear to the subproblem input size . Algorithm B solves the problem of size n by dividing them into two subproblems of size n 1, conquer the subproblems by solving thenm recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in constant time . Algorithm C solves the problem of size n by dividing them into nine subproblems of size n/3, conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to1. Each subproblem combines the solutions in time square to the subproblem input size (a) Write down the recurrence equation and give the tightest asymptotic upper bound (big-O) of each of these algorithms (b) Which algorithm is the fastest?

Explanation / Answer

the recurrence equation is O(n^2.322)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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