Solve using Masters theorem
2T (n/2) + n log n
Simple master theorm not apllied here.
You can use extended master theorm. which gives (n log2n ).
we know,
T(n) = a t(n/b) + Θ(nk .logpn) a=2, b=2 ,k=1 and p=1 so the condition is a=bk
and p>=-1 so T(n)=(nlog 22)*log p+1n so it is n*log2n
64.3k questions
77.9k answers
243k comments
79.7k users