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

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.

-
$$T(n) = T(n/5) + T(4n/5) + \alpha \implies T(n) = n - \alpha$$ – user17762 Sep 13 '12 at 7:33
@Marvis No. Try $T(n)=42\cdot n-\alpha$. – Did Sep 13 '12 at 8:08
@did Yes. $T(n) = k n - \alpha$. – user17762 Sep 13 '12 at 8:38
@Chan $O(1)$ is a function of $n$. What makes this harder than $g(n)=1$? – Erick Wong Sep 13 '12 at 14:58

$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)$.
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.