I was told the answer is (n lg n) but I am not sure. Suppose you have an algorithm that operates on a set of data with n elements. If therecurrence formula that computes the time requirement for the algorithm is given byT(n) =87(C(1)+ Dna. nlgnb. n² lg nc. n²d. n³e.if n > 1if n = 1where D and C are constants, which of the following gives the order of complexity of thealgorithm?none of the other answers

The Master Theorem is used to calculate the time complexity of recurrence relations in a direct way.The Master Theorem works only when formula for solving recurrence relations is T(n) = aT(n/b) + f(n), where a>=1, b>1where,n = size of input,a = no. of subproblemsn/b = size of each subproblemf(n) = cost of work done outside the recursive callThe Master Theorem has three cases:If f(n) is O(nc) where c<logb a, then T(n) is O(nlogb a).If f(n) is Θ(nlogb a logk n) where k≥0, then T(n) is Θ(nlogb a logk+1 n).If f(n) is Ω(nc ) where c>logb a, if a f(n/b) ≤ kf(n) for some constant k<1 and sufficiently large n, then T(n) is Θ(f(n)).GivenRecurrence relation is: T(n)=8T(n/2)+DnThe Master Theorem has the following form: T(n)=aT(n/b)+f(n)In this case, we have: a=8, b=2, f(n)=Dnlogb a = log2 8 = 3Since f(n) = Dn = O(n1), we are in Case 1, and f(n) is O(nlogb a) because 1<3.Therefore, the time complexity of the algorithm is:T(n)=O(nlogb a)=O(n3)Recurrence relation T(n)=8T(n/2)+Dn is n3So, the correct answer is: d.