1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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

| cite | improve this answer | |
$\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.