# asymptotics – Recurrence relations and induction: guessing the right bound

For sure, $$T(sqrt{n})leq T(n)$$, so $$T(n)leq 2T(n-1)+n$$, but this produces an exponential upper bound, which is correct but to big to be useful.

Anyway, in this case if we start from the solution of the recurrence $$S(n)=S(n-1)+O(n)$$, which is $$O(n^2)$$, we observe that $$S(sqrt{n})=O(n)$$, so also the solution of $$T(n)=T(sqrt{n})+T(n-1)+O(n)$$ is in $$O(n^2)$$.

I have to admit that this approach doesn’t seem (also to me) very formal, so I’ve confirmed that guess by explicit calculation.
Indeed, suppose $$T(n)=an^2+bn+c$$, then $$T(sqrt{n})+T(n-1)+n=an^2+(1-a)n+bsqrt{n}+a-b+c$$: we have equality if $$a=1$$, $$b=0$$ and $$c=-1$$, so $$T(n)=n^2-1$$. Clearly, this is not an exact solution as it depends on the starting point, I mean, it is correct only if $$T(1)=0$$; in general you have to check that $$T(n)=O(n^2)$$ (actually, $$T(n)=Theta(n)$$) by induction.

So, returning to your question: no, you cannot simply split the equation and take the solution with larger order of growth.
E.g., consider the recurrence $$T(n)=T(n^{3/4})+T(n-1)+n$$: if $$S(n)=O(n^2)$$, then $$S(n^{3/4})=n^{3/2}$$ is no more a $$O(n)$$, so we cannot conclude as before.
But if you have a recurrence of the form $$T(n)=T(f(n))+T(g(n))+O(h(n))$$
(with reasonable assumption of functions $$f,g,h$$, I mean, positive, monotone, …)
and the solution of, say, $$S(n)=S(g(n))+O(h(n))$$ is such that $$S(f(n))=O(h(n))$$, then you can make the (more than) reasonable assumption that $$T(n)=O(S(n))$$, and confirm it by induction.