Asymptotics of a recurrence defined with two variables
Interesting recurrence. Let's take a crack at this. Just a heads up, this answer is a bit wordy/explicit. 

Clearly the first issue/difficulty is that we're trying to define this in terms of two variables ($n_1, n_2$). This seems hard so let's go ahead and redefine this relation:

$$t(n_1 + n_2) \geq t(n_1) + t(n_2) + c \log_2(1 + n_2)$$

Let $\alpha$ be a constant such that $0 &lt; \alpha \leq \frac{1}{2}$. We can then define $n$ and $n'$ as:

$$n = n_1 + n_2$$
$$n' = \lceil \alpha n \rceil$$

You also asked for the smallest function that satisfies this. I'm taking this to mean when the left side if smallest, so we will redefine $t(n_1 + n_2)$ as:

$$t(n) = t(n') + t(n - n') + c \log_2(1 + n - n')$$

or possibly:

$$t(n) = t(n') + t(n - n') + c \log_2(1 + n')$$

If we were just looking for the upper bound of $t(n_1 + n_2)$ then we would only need the first case because it is the worst case, but we are looking for the tight bound. In any case, we now have a more manageable form of our recurrence.

You can prove by induction that:

$$an \leq t(n) \leq bn - c\log_2 n + d$$ 

for some constants $a,b,c &gt; 0$. Constant $d$ will be defined momentarily.

Induction step for Lower Bound

$$
\begin{align}
t(n) &amp; = t(n') + t(n - n') + c \log_2(1 + n - n')\\
 &amp; \geq t(n') + t(n - n') + c \log_2(1)\\
 &amp; = an' + an - an' + 0\\
 &amp; = an
\end{align}
$$

Induction step for Upper Bound

$$
\begin{align}
t(n) &amp;= t(n') + t(n - n') + c \log_2(1 + n - n')\\
 &amp;\leq t(n') + t(n - n') + c \log_2 n\\
 &amp;= bn' - c\log_2n' + d + b(n-n') - c\log_2(n-n') + d + c \log_2 n\\
 &amp;= bn + 2d - c\log_2n' - c\log_2(n-n') + c \log_2 n\\
 &amp;= bn + 2d - c\log_2(n'(n-n')) + c \log_2 n\\
 &amp;= bn + 2d - c\log_2(\alpha n(n- \alpha n)) + c \log_2 n\\
 &amp;= bn + 2d - c\log_2(n^2 \alpha (1- \alpha )) + c \log_2 n\\
 &amp;= bn + 2d - 2c\log_2 n - c\log_2( \alpha (1- \alpha )) + c \log_2 n\\
 &amp;= bn - c \log_2 n + 2d - c\log_2( \alpha (1- \alpha ))
\end{align}
$$

Now we can define $d$ in terms of constants $c$ and $\alpha$.

$$ d = c\log_2( \alpha (1- \alpha ))$$

Therefore

$$t(n) \leq bn - c \log_2 n + d$$

Clearly $an \leq t(n) \leq bn$. It's worth noting this is because $d$ will always be negative.

Now we can conclude

$$t(n_1 + n_2) = \Theta(n_1 + n_2)$$