# Divide and Conquer in big O notation

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!)

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

• If $T(n) = \cdots+\cdots+O(n)$ then I do not see how you can conclude $T(n)$ can be smaller than $O(n^1)$ – Henry Jun 8 '15 at 8:45
• @Henry - see revised, I forgot a factor in the theorem. – nbubis Jun 8 '15 at 8:49
• Pretty cool idea! $p \approx 0,76$ – BigOO Jun 8 '15 at 8:58
• How do you solve for p $$\left(\frac{1}{7}\right)^p+\left(\frac{5}{7}\right)^p=1$$ ? – Syed Souban Aug 14 '19 at 17:25
• @SyedSouban - You don't need to. As long as the $p<1$, then the result will be $O(n)$. – nbubis Aug 17 '19 at 17:38

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