Find solution to recurrence: T(N) = 2 T(N/4 + √N) + (√10) N

Question

While solving a complex recurrence equation like this T(N) = 2 T(N/4 + √N) + (√10) N ;T(1) = 1

I tried to make some change of variables to make it easy and solve it by master theorem but i failed ,so i take the dominant one so it will be: T(N) = 2 T(N/4) + (√10) N so it is T(N)=Θ(N). Is that true or not ?

Answer 1

Trying to unroll recursion or to make a substitution left me nowhere. So the only thing I was able to do is to see that for any sufficiently large n (above 64). You can select any number (not just 8), bigger than 4.

So you end up with

Solving this with master's theorem you see that it falls in the first case with .

Therefore the solution is Θ(N) which is the same as you wondered.