If you are using divide and conquer to solve the problems, then your solution mu

Question

If you are using divide and conquer to solve the problems, then your solution must clearly and specify describe each of the following steps:

• Dividing the problem into sub problems

• Solving sub problems

• Merging solutions of sub problems.

Then, you must derive a recurrence relation for the run-time of the algorithm, and solve the recurrence relation. In this PA, you may assume that n is a power of 2 (if it helps).

Solve the following recurrences. You can not use master theorem to solve them. You must show the steps in your derivation.

(a) T(n) = T(n/3) + T(2n/3) + cn.

(b) T(n) = T(n/5) + cn.

(c) T(n) = 2T(n/2) + n log5(7)

Explanation / Answer

I am attaching 2 links for the images, if I reduce the size then it is difficult to understand.

https://drive.google.com/file/d/0B31UuDZvXM1bRjc1blBlUTJxZnNfdmR2dW81dlItQWQ4bGdR/view?usp=sharing

https://drive.google.com/open?id=0B31UuDZvXM1bOUdKRDlGa0l5NmxXMVdyN1VFQ0FVUUVQRU13

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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