(a)
T (n) = 0.5n + T (n − 1).
T(n-1) = 0.5(n - 1) + T(n - 2)
T(n-2) = 0.5(n - 2) + T(n - 3)

T(n) = 0.5n + [0.5(n - 1) + T(n - 2)]
T(n) = 0.5n + 0.5(n - 1) + T(n - 2)
T(n) = 0.5n + 0.5(n - 1) + [0.5(n - 2) + T(n - 3)]

T(n) = 0.5(n + (n - 1) + (n - 2) + ... + 1) = 0.5(n(n+1)/2) = n(n+1)/4

(b)
T(n) = 2T(n/2) + 1
T(2^k) = 2T(2^(k-1)) + 1

Let S(m) = T(2^m)

S(m) = 2S(m-1) + 1
S(m-1) = 2S(m-2) + 1
S(m-2) = 2S(m-3) + 1

S(m) = 2[2S(m-2) + 1] + 1
= 4S(m-2) + 3
= 4[2S(m-3) + 1] + 3
= 8S(m-3) + 7
= (2^m)S(1) + 2^(m-1)
= O(2^m)

S(m) = 2^m + 1

T(n) = T(2^k) = S(k) = 2^k +1 = 2^(log n) + 1= n + 1

(c)
T(n) = T(sqrt(n)) + 1
T(2^k) = T(2^(k/2)) + 1

Let S(m) = T(2^m)

S(m) = S(m/2) + 1
S(m) = log m

T(n) = T(2^k) = S(k) = log k = log (log n)