0
$\begingroup$

I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$ This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-1)+n$$ and $$T(n)=T(\sqrt{n})+1$$ because they were both easier to solve.

Does it makes sense to guess an upper bound for the original recurrence relation (and try to confirm that guess through induction) based on the complexities I obtained for both for these (i.e. use the one with larger order of growth for example)?

If not then what are some ways to find/guess an upper bound for such a relation?

$\endgroup$

1 Answer 1

1
$\begingroup$

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+b\sqrt{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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.