Solve the recurrence an=2an/2+nlog2na_n = 2a_{n/2} + n \log_2 nan=2an/2+nlog2n for n=2kn=2^kn=2k with a1=1a_1=1a1=1. What is the closed-form complexity?
Θ(nlog2n)\Theta(n \log_2 n)Θ(nlog2n)
Θ(nlog22n)\Theta(n \log_2^2 n)Θ(nlog22n)
Θ(n2log2n)\Theta(n^2 \log_2 n)Θ(n2log2n)
Θ(nlog2n+n)\Theta(n \log_2 n + n)Θ(nlog2n+n)