Masters method with sqrt

Question

I was doing

$$T(n)=4T(n/2)+n^3+\sqrt{n}$$

Without the square root, it is a basic example but with a square root there, I dont know what to do.

I think the 3rd parameter of the masters method will be applied but I just dont know what to do with the square root.

As it is not in the form of

$$T(n)=aT(n/b)+f(n)$$

How should it be solved or should I use the tree method for this?

Answer 1

1) you say that the equation is not of the form

$$T(n)=aT(n/b)+f(n).$$

But it is, with $a=4,b=2,f(n)=n^3+\sqrt n$.

2) if you feel uncomfortable with $f(n)=n^3+\sqrt n$, as the equation is linear you can process the two terms separately, then join the two solutions.

3) the term $\sqrt n$ is of a lower order than $n^3$, so that you can neglect it without changing the asymptotics of the solution.