How to solve this recurrence relation $T(n) = T(n/5) + T(4n/5) + O(1)$

Question

Given the recurrence: $$T(n) = T(n/5) + T(4n/5) + O(1)$$ The annoying part is $O(1)$. If it were some $g(n)$, then I could use recursion tree on $n$, but there is no such $n$ to start with. So I wonder what method can be used in this case? Any idea would be greatly appreciated.

Answer 1

$O(1)$ means bounded, hence, for example, $T(n)\leqslant T(n/5)+T(4n/5)+a$. Choose $N$ and $c$ such that $T(n)\leqslant cn-a$ for every $n\leqslant N$. Then, for every $n\leqslant5N/4$, $$ T(n)\leqslant(cn/5-a)+(c4n/5-a)+a=cn-a. $$ Repeating this and using $(5/4)^kN\to+\infty$ when $k\to+\infty$, one sees that $T(n)\leqslant cn-a$ for every $n$, thus, $T(n)=O(n)$.

Answer 2

Assuming everything in sight is positive, your initial recurrence is equivalent to saying that there exists a $c>0$ such that $$ T(n) \le T(n/5)+T(4n/5)+c $$ for all $n$ sufficiently large. Now, "if thy constant offends thee, pluck it out". Let $U(n)=T(n)+c$ and you'll have $$ \begin{align} T(n)+c &\le T(n/5)+T(4n/5)+2c\\ &=T(n/5)+c-c+T(4n/5)+c-c+2c \end{align} $$ so you have $$ U(n)\le U(n/5)+U(4n/5) $$ which you've said you can solve. If you do, you'll find $U(n)=O(n)$, and hence $T(n)=O(n)$ as well.