Problem 4. (25 points) Suppose that we have designed three divide-and-conquer al

Question

Problem 4. (25 points) Suppose that we have designed three divide-and-conquer algorithms that solve a particu- lar problem, where the input size is n. The first one solves four subproblems of size n/2 and the cost of combining the solutions of the subproblems to obtain a solution for the original problem is n2. The second solves three subproblems of size n/2 and requires n2 Vn time for combining the solutions. The third solves five subproblems of size n/2 and requires n logn time for combining the solutions. Assume that all three take (1) when n- 1. Which algorithm would you choose and why? Show your work using the Master method. Answer:

Explanation / Answer

Let T(n) be the total time complxity , For first One, There are 4 subproblems of size n/2 and cost is n2 means The Recurrance is

1 . T(n) = 4T(n/2) + n2

Let T(n) be the total time complxity , For Second One, There are 3 subproblems of size n/2 and cost is n2n means The Recurrance is

2 . T(n) = 3T(n/2) + n2n

Let T(n) be the total time complxity , For Third One, There are 5 subproblems of size n/2 and cost is nlogn means The Recurrance is

3 . T(n) = 5T(n/2) + nlogn


Solving (1) by masters method we get ,
1 . T(n) = 4T(n/2) + n2 Comparing it with aT(n/b) + f(n) => a = 4, b = 2 and f(n) = n2   
g(n) = nlog 24 = n2

f(n) = g(n) By case 2 of masters theorem we get O( n2 log n ) ---- (1)



Solving (2) by masters method we get ,
2 . T(n) = 3T(n/2) + n2n Comparing it with aT(n/b) + f(n)  => a = 3, b = 2 and f(n) = n2n
g(n) = nlog 23 = n1.58

f(n) > = g(n) = n2+0.5 = n2.5 >  n1.58

f(n) >= g(n) By case 3 of masters theorem we get O( n2n) ---- (2)

Solving (3) by masters method we get ,
3. T(n) = 5T(n/2) + nlogn Comparing it with aT(n/b) + f(n)  => a = 3, b = 2 and f(n) = n2n
g(n) = nlog 25 = n2.32

f(n) <= g(n) = nlogn <= n2.325  

f(n) <= g(n) By case 1 of masters theorem we get O( nlog2 5 ) => O( n2.325  ) ---- (3)


We know that n2n >>> n2.325 >>>> n2 log n By Ordering


Hence we can say that we will choose ALGORITHM --> 1 [Answer] , we need to choose that solve the problem in less time

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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