Given T(n)=2T(n2)+nT(n) = 2T(\frac{n}{2}) + nT(n)=2T(2n)+n with T(1)=1T(1) = 1T(1)=1. Using the Master Theorem, what is the asymptotic complexity O(f(n))O(f(n))O(f(n))?
O(n)O(n)O(n)
O(nlogn)O(n \log n)O(nlogn)
O(n2)O(n^2)O(n2)
O(logn)O(\log n)O(logn)