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!)
[Math] Divide and Conquer in big O notation
algorithmsasymptotics
Related Solutions
Intuitively, the idea is that the "order" of a function is that of its highest-order term. In $x^4 + x^2 + 1$, you can usually ignore everything except the $x^4$, and say that it is $O(x^4)$ and not $O(x^d)$ for any smaller $d < 4$. Similarly $x^3 + 1$ is of the order of $x^3$, and in general a polynomial of degree $d$ is of the order of $x^d$.
So in your first function $f(x) = f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$, the numerator is of order $x^4$ and the denominator is of order $x^3$, so the fraction $f(x)$ is of order $\frac{x^4}{x^3} = x$.
That's the idea of what's really going on, but to prove it formally, you can do the division: write $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1} = x + \frac{x^2 - x + 1}{x^3 + 1}$, and observe that the remainder term $\frac{x^2 - x + 1}{x^3 + 1} = \frac{1}{x+1} \to 0$ as $x \to \infty$, so $f(x) = O(x)$ and not $O(x^{1 - \epsilon})$ for any $\epsilon > 0$.
You don't even have to do the division completely: just get rid of the $x^3$ terms from both numerator and denominator. Observe that $$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1} = \frac{(x^4 + x^2 +1)/x^3}{(x^3 + 1)/x^3} = \frac{x + \frac{1}{x} + \frac{1}{x^3}}{1 + \frac{1}{x^3}}$$ and you can prove directly from this that $f(x) = O(x)$.
Similarly, for the second function, $f(x) = \frac {x^4 + 5 \log x}{x^4 + 1}$, both numerator and denominator are of the same order $x^4$, so you should expect the fraction to be $O(1)$. You can prove it by writing $$f(x) = \frac {x^4 + 5 \log x}{x^4 + 1} = \frac {(x^4 + 5 \log x)/x^4}{(x^4 + 1)/x^4} = \frac{1 + \frac{5 \log x}{x^4}}{1 + \frac{1}{x^4}} $$ and proving from there that $f(x) = O(1) = O(x^0)$.
(E.g. you can show that, for $c_1 = \frac12$ and $c_2 = 2$ (say) and sufficiently large $x$, we have $c_1 \le f(x) \le c_2$, since $f(x) \ge \frac{1}{1 +\frac1{x^4}} \ge \frac{1}{2}$ when $x \ge 1$, and similarly $f(x) \le \frac{1 + \frac{5\log x}{x^4}}{1} \le 2$ when $\frac{5 \log x}{x^4} \le 1$, which again is true for sufficiently "large" $x$. Actually in this case any constants $c_1 < 1 < c_2$ will do, since $\lim_{x\to\infty} \frac{f(x)}{x} = 1$, but we don't need all this just to prove that $f(x) = O(1)$.)
Best Answer
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)$.