2
$\begingroup$

I have a problem: the algorithm is dividing the given problem into two subproblems - one is 3/5 big and another is 4/5 of the size of the problem - and then merges those two parts together in a linear time. I've found, that you can write it as

$$T(n) = T(3n/5) + T(4n/5) + O(n)$$

I have to rewrite it into a Big O notation, but I don't know, how to proove, which one to use - I personally think, that it will be a $O(n^2)$, but without a proof, it is nothing. Can you, please, help me?

$\endgroup$
1
$\begingroup$

Start by writing out the recursion for a few levels and see what happens. For convenience, I am going to write your $O(n)$ term as $Cn$. There is no harm in this since we can upperbound that function by $Cn$ for sufficiently large $C$. Then, note that $T(4n/5)\geq T(3n/5)$ so the dominant term will come from $T(4n/5)$. Since we are only concerned with an upper-bound, I will replace the $T(3n/5)$ with $T(4n/5)$.

\begin{align*} T(n) &= T(3n/5)+T(4n/5) + Cn \\ &\leq 2T(4n/5) + Cn \end{align*}

Using the "new" upperbound as the definition for recursion, write out a few steps to look for a pattern:

\begin{align*} T(n) &\leq 2T(4n/5) + Cn \\ &\leq 2(2T(4^{2}n/5^{2})+C4n/5) + Cn \\ &=2^{2}T(4^{2}n/5^{2})+2C(4n/5)+Cn \\ &\leq 2^{2}(2T(4^{3}n/5^{3})+C(4^{2}n/5^{2}))+2C(4n/5)+Cn \\ &=2^{3}T(4^{3}n/5^{3})+ Cn(4^{2}/5^{2}+4/5 + 1) \\ &\vdots \\ &\leq 2^{k}T(4^{k}n/5^{k}) + Cn\sum_{i=0}^{k}(4/5)^{i} \end{align*}

Then, we just decide how large $k$ must be so that $(4/5)^{k}n\approx 1$. This means that $\lg(n)=k\lg(5/4)$ or $k=\lg(n)/\lg(5/4)$. An upperbound on your runtime is then $2^{k}+Cn\sum_{i=0}^{\infty}(4/5)^{i}$. Note that $2^{k}=(2^{\lg(n)})^{1/\lg(5/4)}$. According to google calculator, $1/\lg(5/4)\approx 3.1$ so $2^{k}\approx n^{3.1}$ The take home message is that the $Cn$ term is not significant compared to the $2^{k}$. So, you can say that $$T(n)=O(2^{\lg(n)/\lg(5/4)}).$$ You can also say that $T(n)=O(n^{\alpha})$ for any $\alpha\geq 1/\lg(5/4)$. You might be able to get a slightly tighter upperbound by not replacing $T(3/5)$ with $T(4/5)$ but the computation will be more involved. (Also, $O(f(n))$ is just an upperbound, it doesn't have to be the "best possible upperbound.")

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You can shorten this by just using the master method bounding between $2T(3n/5)$ and $2T(4n/5)$, but that gives you a pretty wide range... somewhere between $\Theta(n^{1.357})$ and $\Theta(n^{3.106})$. If you plot the recurrence, you do get $\Theta(n^2)$... question is how to get that bound. $\endgroup$ – Barry Jun 3 '15 at 15:30
  • $\begingroup$ @Barry, the $n^2$ was a guess. And he wanted $O(f(n))$... I went with $2T(4/5)$ because I can guarantee that the bound I get is true. I illustrated the method since in this case the master method cannot be used to get "the right answer" because of the two terms. $\endgroup$ – TravisJ Jun 3 '15 at 15:39
  • $\begingroup$ @Barry, I personally don't like the master method simply because it reduces the problem to plugging numbers into a formula and people stop thinking about the "why" part and lose intuition. If you just need a quick answer, it is great. If you want to understand why... not so much. $\endgroup$ – TravisJ Jun 3 '15 at 15:41
  • $\begingroup$ That argument is basically objecting to all algorithms, no? $\endgroup$ – Barry Jun 3 '15 at 15:45
  • $\begingroup$ @Barry, to rote-algorithms in particular instances. If you only need the answer then any algorithm is fine. If you want understanding, then the algorithm can sometimes thwart that attempt. It all depends on context. For example, in this case you suggest applying the method to a function which doesn't fit the algorithm. The modified versions do $2T(3n/5)$ or $2T(4n/5)$, but to assert that the $\Theta$ of the original is in-between presupposes that the the function actually has a $\Theta$ value (matching upper-lower bounds) which in practice it may not have. $\endgroup$ – TravisJ Jun 3 '15 at 15:49

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.