Question

Consider a divide and conquer algorithm that divides each problem into 2 sub-problems of size ( 3n4 ) each. Write the recurrence relation for this algorithm and compute the time complexity using the master theorem.

a) ( T(n) = 2Tleft(3n4right) + O(1) ), ( O(nlog n) )
b) ( T(n) = 2Tleft(3n4right) + O(n) ), ( O(nlog n) )
c) ( T(n) = 2Tleft(3n4right) + O(1) ), ( O(n^2) )
d) ( T(n) = 2Tleft(3n4right) + O(n) ), ( O(n^2) )

Answer 1

The correct option is (a) (T(n) = 2T(3n/4) + O(1)), (O(nlog n)). The time complexity can be computed using the Master Theorem.

Step-by-step explanation:

The correct option is (a) (T(n) = 2T(3n/4) + O(1)), (O(nlog n)).

The given recurrence relation represents a divide and conquer algorithm where each problem is divided into two sub-problems of size (3n/4) each. The time complexity of this algorithm can be computed using the Master Theorem.

The Master Theorem states that for a recurrence relation of the form T(n) = aT(n/b) + f(n), where a >= 1 and b > 1, and f(n) is an asymptotically positive function, the time complexity is given by:

1. If f(n) = O(n^c) for some constant c >= 0, and a < b^c, then T(n) = O(n^c).
2. If f(n) = O(n^c) for some constant c > 0, and a = b^c, then T(n) = O(n^c log n).
3. If f(n) = O(n^c) for some constant c > 0, and a > b^c, and if a f(n/b) <= kf(n) for some constant k < 1 and sufficiently large n, then T(n) = O(f(n)).