Question. To within a constant factor, what is a solution to recurrence T(n) = 2T(n/2) + √n?
Answer. T(n) = Θ(n).