Self Doubt[Gate Question]

Question

Let T(n)

be a function defined by the recurrence

T(n)=2T(n/2)+√n

for n≥2 andT(1)=1

Can someone please explain solution of this using back substitution

Answer 1

Hope it clears your doubt :) (please excuse my untidyness)

Comments

Also You can do directly by using master theorem in the form aT(n/b)+O(n^.5)

here a=2,b=2,k=0.5 by the formula

if a>b^k, T(n)=O(n^logba) b is base,

=O(n)