For the recurrence T(n)=3T(⌊n/2⌋)+nT(n) = 3T(\lfloor n/2 \rfloor) + nT(n)=3T(⌊n/2⌋)+n, what is the asymptotic time complexity?
Θ(nlogn)\Theta(n \log n)Θ(nlogn)
Θ(nlog23)\Theta(n^{\log_2 3})Θ(nlog23)
Θ(n2)\Theta(n^2)Θ(n2)
Θ(n3)\Theta(n^3)Θ(n3)