Solve the recurrence relation and give the exact solution No

Solve the recurrence relation and give the exact solution (Not just the complexity calss): T(n) = 2T(n/2) + sqrt(n)

Answer should be: T(n) = (1 / sqrt(2) -1) (sqrt(2)n - sqrt(n))

Solution

Answer:

T(n) = 2T(n/2) + n^1/2

Using Masters Theorm, we have

a = 2 , b = 2 , therefore log2 base 2 = 1 , c = 1/2 , that means c < loga base b , therefore T(n) = theta(n^loga base b) = > T(n) = (n^1) => T(n) = theta(n)