Big O notation proof for a divided problem 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?
 A: 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.")
