T(n) = (1/n) Sum T(n-i) + T(i) + Θ(n)
= (2/n) Sum T(i) + Θ(n)
Telescope the sum,
(n+1) T(n+1) - n T(n) = 2 Sum T(i) + (n+1) Θ(n+1)
- (2 Sum T(i) + n Θ(n))
= 2 T(n+1) + C ((n+1)2 - n2)
so,
(n-1) T(n+1) = n T(n) + &Theta(n)telescope this sum as well,
(1/n) T(n+1) = 1/(n-1) T(n) + 1/(n(n-1))Θ(n)
= 1/(n-1) + 1/(n-2) + ...
= Θ(log n)