2
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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