The recurrence becomes:
    T(1) = 0
    T(n) = n/2 + T(n/2)
Then solve the summation using the formula for the exact solution.