2. A divide-and-conquer algorithm solves a problem by dividing its given instanc

Question

2. A divide-and-conquer algorithm solves a problem by dividing its given instance into several smaller instances, solving each of them recursively, and then, if necessary, combining the solutions to the smaller instances into a solution to the given instance. Assuming that all smaller instances have the same size n/b, with a of them being actually solved, we get the following recurrence valid for n-bk, k-0,1,2 T(n) - aT(n/b) + f(n), where a 2 1, b2 2, and f(n) is a function that accounts for the time spent on dividing the problem into smaller ones and combining their solutions. (a) Show that the following formula is the solution to this recurrence for n-b*. logb n f(b') ai The order of growth of solution T(n) depends on the values of the constants a and b and the order of growth of the function f(n) (b) What is T(n), if a = 3, b 2, and f(n) = 1, where T(1) = c which is a constant? (c) What is T(n), if a = 3, b = 2, and f(n) = n, where TCI) = c, which is a constant? (d) What is T(n), if a-3, b -2, and f(n)- log2 n, where T(1)-c, which is a constant?

Explanation / Answer

Solution:

a is solved, please repost others.

a)

The recurrence for divide and conquer is mentioned as follows:

For and is the time spent in dividing the problem.

Consider

        

Expand the function T(n) after a

Expand the function T(n) after a

Proceed upto k and Take common

…(1)

Assume n=bk .

Since

Now equation (1) will be

The equation can be written as a summation.

Hence it is proved that

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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