Divide and Conquer in big O notation

Question

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it can be rewritten to $T(n) = T(n/7) + T(5n/7) + O(n)$. Is there a simple way for rewriting this whole thing into big O notation? (Also if you can explain your procedure to me, so I can start using Big O notation on my own, I will be happy!)

Answer 1

By the Akra–Bazzi method, we have:

$$T(n) = T(n/7)+T(5n/7)+g(n)$$ $$a_1 = 1, a_2 = 1, b_1 = 1/7, b_2 = 5/7$$ We must find $p$ such that: $$\left(\frac{1}{7}\right)^p+\left(\frac{5}{7}\right)^p=1$$ Since $p<2$ in this case, then the Akra–Bazzi method gives you that: $$T(n) = \Theta(n^{p}(1+n^{1-p}))=\Theta(n)$$

Answer 2

The suspicion must be that $T(n) \in O(n)$.

Suppose that you actually have $$T(n) \le T(n/7) + T(5n/7) + cn$$ for some $c$. Then following the recursion down you have $$ T(n) \le c n \left(1 + (6/7) + (6/7)^2 + \cdots \right) = 7cn $$ and thus $T(n)\in O(n)$.