Question

You are an algorithm designer and you came up with four different divide-and-conquer algorithms for some problem Q. Those four algorithms are described below in parts (1), (2), (3), and (4). You wrote those descriptions a long time ago so now you want to remind yourself, for each one of them, what was the corresponding recurrence relation and provide an upper bound on the running time. So first give the recurrence then solve it using any method of your choice (show your work).

1. If you solve 4 sub-problems of size n/5, then the cost of combining the solutions of the sub-problems to obtain a solution for the original problem is 2n + 5;

2. If you solve 14 sub-problems of size n/4, then the cost for combining the solutions is 123;

3. If you solve 2 sub-problems of size n/2, then the cost for combining the solutions is 5n 3 + 2n 2 + 3;

4. If you solve 3 sub-problems of size 2n/3, then the cost for combining the solutions is 4n.

Answer 1

Ans: After closer observation it is quite clear that all the algorithms mentioned in the question can be easily solved using Master method.

Master Method:

Master method is mainly derived from recurrence tree method. If Recurrence relation is of the form:

where a >= 1 and b > 1

Then there exist following three cases:

Case 1: If f(n) = Θ(n^c) where c < Log_ba then T(n) = Θ(n^Log_ba)

Case 2: If f(n) = Θ(n^c) where c = Log_ba then T(n) = Θ(n^cLog n)

Case 3: If f(n) = Θ(n^c) where c > Log_ba then T(n) = Θ(f(n))

Solution: Each recurrence relation is of the form:

(no. of sub problems)*T(size) + (cost of combining)

Hence,

1)

Using Master Method,

a = 4; b = 5; c = 1; f(n) = 2n+5

Log_b(a) = Log₅(4) = 0.8613 < c

Hence, According to Case 3

=>

2)

Using Master Method,

a = 14; b = 4; c = 0; f(n) = 123

Log_b(a) = Log₄(14) = 1.9037 > c

Hence, According to Case 1

=>

3)

Using Master Method,

a = 2; b = 2; c = 3; f(n) = 5n³+2n²+3

Log_b(a) = Log₂(2) = 1 < c

Hence, According to Case 3

=>

4)

Using Master Method,

a = 3; b = 3/2 = 1.5; c = 1; f(n) = 4n

Log_b(a) = Log_1.5(3) = 2.7095 > c

Hence, According to Case 1

=>