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.
How to solve this recurrence relation $T(n) = T(n/5) + T(4n/5) + O(1)$
-
0@Chan $O(1)$ is a function of $n$. What makes this harder than $g(n)=1$? – 2012-09-13
2 Answers
$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.