$Θ(n) + O(n) = ?$ (recurrence equation)

Question

If I have a recurrence equation like

$$T(n) \leq T(n/2) + Θ(n) + O(n),$$ then is this expression equal to $T(n) \leq T(n/2) + Θ(n)$? Or is that expression equal to: $T(n) \leq T(n/2) + O(n)$?

Answer 1

Your inequality says basically that there exist $f$ and $g$ such that

$$ T(n) \le T(n/2) + f(n) + g(n) $$

where $f(n)$ is $\Theta(n)$ and $g(n)$ is $O(n)$.

Since any function that is $\Theta(n)$ is also $O(n)$ and $\Theta(n)+\Theta(n)$ is $\Theta(n)$, you could equivalently say that $$ T(n) \le T(n/2) + \Theta(n) $$ ie. your first variant.

Answer 2

What you have is $T(n) \le T(n / 2) + f(n) + g(n)$, where there are positive constants $c_1$, $c_2$, and $c_3$ such that $c_1 n \le f(n) \le c_2 n$ and $0 \le g(n) \le c_3 n$. Adding them up, $c_1 n \le f(n) + g(n) \le (c_2 + c_3) n$, i.e., $f(n) + g(n) = \Theta(n)$.