For the recurrence T(n)=2T(⌊n/2⌋)+1T(n) = 2T(\lfloor n/2 \rfloor) + 1T(n)=2T(⌊n/2⌋)+1 with T(1)=1T(1) = 1T(1)=1, which asymptotic bound is correct?
T(n)=Θ(logn)T(n) = \Theta(\log n)T(n)=Θ(logn)
T(n)=Θ(n)T(n) = \Theta(n)T(n)=Θ(n)
T(n)=Θ(nlogn)T(n) = \Theta(n \log n)T(n)=Θ(nlogn)
T(n)=Θ(n2)T(n) = \Theta(n^2)T(n)=Θ(n2)