The recurrence T(n)=T(⌊n/2⌋)+lognT(n) = T(\lfloor n/2 \rfloor) + \log nT(n)=T(⌊n/2⌋)+logn with T(1)=1T(1) = 1T(1)=1 describes a recursive algorithm. What is Θ(T(n))\Theta(T(n))Θ(T(n))?
Θ(logn)\Theta(\log n)Θ(logn)
Θ(log2n)\Theta(\log^2 n)Θ(log2n)
Θ(n)\Theta(n)Θ(n)
Θ(n)\Theta(\sqrt{n})Θ(n)