If T(n)=2T(n)+log2nT(n) = 2T(\sqrt{n}) + \log_2 nT(n)=2T(n)+log2n, let m=log2nm = \log_2 nm=log2n. What is the recurrence in mmm?
S(m)=2S(m/2)+mS(m) = 2S(m/2) + mS(m)=2S(m/2)+m
S(m)=2S(m)+mS(m) = 2S(m) + mS(m)=2S(m)+m
S(m)=S(m/2)+m2S(m) = S(m/2) + m^2S(m)=S(m/2)+m2
S(m)=S(m/2)+mS(m) = S(m/2) + mS(m)=S(m/2)+m