Use the Master Theorem to find the asymptotic complexity of T(n)=2T(n4)+nT(n) = 2T\left(\frac{n}{4}\right) + \sqrt{n}T(n)=2T(4n)+n.
Θ(n)\Theta(\sqrt{n})Θ(n)
Θ(nlogn)\Theta(\sqrt{n} \log n)Θ(nlogn)
Θ(n)\Theta(n)Θ(n)
Θ(nlogn)\Theta(n \log n)Θ(nlogn)