Suppose Tn 3 Tn2n4 is the recurrence equation for a divide

Suppose T(n) = 3 T(n/2)+n/4 is the recurrence equation for a divide - and conquer recursive solutiom problem.

a. Each step of the recursion, we divide a problem into how many subproblems?

b. When we divide a problem into subproblems, how many inputs are used in each of the subproblems.

Solution

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

This is in the form T(n)=aT(n/b)+f(n),   where a is the number of sub problem, n/b is the size of each sub problem and f(n) is the cost of the problem

Here a=3, b=2, f(n) =n/4

So

a) At each step of recursion, we divide the problem into 3 sub problems

b) There are n/b =n/2 number of input are used in each of the sub problems