How do you solve these recurrence relations for a closed form?

Question

I'm not sure what methods are used to solve recurrence relations for a big-$O$ notation. Thinking about the problem conceptually doesn't really help me, but I feel like I could use some form of induction to come up with a tight upper-bound.

$$T(n) = T(\frac{n}{3})+T(\frac{2}{3}n)+n$$

$$T(n) = T(\frac{n}{7})+T(\frac{4}{14}n)+n$$

Answer 1

Use the Akra-Bazzi method directly. For $T(n) = T(\frac{n}{3})+T(\frac{2}{3}n)+n$, we have $\left(\frac13\right)^p+\left(\frac23\right)^p=1 \implies p=1$, so that the asymptotic behavior is $$T(n)=O\left( n\left( 1+\int_1^n \frac{u}{u^2}du \right)\right)=O(n(1+\ln n))=O(n\ln n)$$

Similarily for $T(n) = T(\frac{n}{7})+T(\frac{4}{14}n)+n$, $\left(\frac17\right)^p+\left(\frac4{14}\right)^p=1 \implies p\approx0.4407$, so that

$$T(n)=O\left( n^{p}\left( 1+\int_1^n \frac{u}{u^{1+p}}du \right)\right)=O\left( n^{p}\left( 1+\frac{n^{1-p}}{1-p}-\frac1{1-p} \right)\right)=O(n)$$

Answer 2

In $T(n) = T\left(\dfrac{n}{7}\right)+T\left(\dfrac{4}{14}n\right)+n$, this is consistent with $T(n) \le \dfrac{n}{1-\left(\frac17+\frac{4}{14}\right)}=\dfrac{7}{4}n$ since you would then have $T\left(\dfrac{n}{7}\right)+T\left(\dfrac{4}{14}n\right)+n \le \dfrac{n}{4}+\dfrac{n}{2} +n = \dfrac{7}{4}n.$ So you can conclude $T(n)$ is $O(n)$.

You could do the same with $T(n) = T\left(\dfrac{n}{5}\right)+T\left(\dfrac{7}{10}n\right)+n$ and $T(n) \le \dfrac{n}{1-\left(\frac15+\frac{7}{10}\right)}=10n$.

But you cannot do the same with $T(n) = T\left(\dfrac{n}{3}\right)+T\left(\dfrac{2}{3}n\right)+n$, since $1-\left(\frac13+\frac{2}{3}\right)=0$.