# Asymptotics of a recurrence defined with two variables

What is the asymptotic behaviour, in Θ notation, of the smallest function that for any $n_1$ and $n_2$ satisfies the following:

$$t(n_1+n_2)≥t(n_1)+t(n_2)+c·\log_2(1+n_2)$$ where $n_1≥n_2≥1$ and $t(1)=1$

I tried to see what happens if $n_1 = n_2$:

$$t(2n)≥t(n)+t(n)+c·\log_2(1+n)$$ $$t(n)≥2t(n/2)+c·\log_2(1+n/2)$$

Also if $n_2=1$:

$$t(n+1)≥t(n)+t(1)+c·\log_2(2)$$ $$t(n)≥t(n-1)+1+c$$

But I am not sure where to go next, or if this is a correct approach.

• Are you sure you understand what two-variable asymptotics are? See here and other posts linked from there for some thoughts. – Raphael May 7 '17 at 19:11
• @Raphael I know, I chose the title to reflect the fact that the function itself is defined with two variables, not that the asymptotics should be two-variable itself. – IllidanS4 wants Monica back May 7 '17 at 19:16
• In which variable should the asymptotic be expressed then? (By the way, are you sure that "the smallest function" is well-defined?) – Raphael May 7 '17 at 19:22

The function $t$ is given by $t(n) = 1$ and for $n>1$, $$t(n) = \min_{1 \leq k \leq n/2} t(n-k) + t(k) + c\log_2(1+k).$$ You can prove by induction that $$t(n) = n + c(n-1).$$ This holds when $n=1$. For the inductive step, \begin{align*} t(n-k) + t(k) + c\log_2(1+k) &= [n-k + c(n-k-1)] + [k + c(k-1)] + c\log_2(1+k) \\ &= n + c(n-2) + c\log_2 (1+k) \\ &\geq n+c(n-2)+c \\ &= n + c(n-1). \end{align*}

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 < \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 > 0$. Constant $d$ will be defined momentarily.

Induction step for Lower Bound

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

Induction step for Upper Bound

\begin{align} t(n) &= t(n') + t(n - n') + c \log_2(1 + n - n')\\ &\leq t(n') + t(n - n') + c \log_2 n\\ &= bn' - c\log_2n' + d + b(n-n') - c\log_2(n-n') + d + c \log_2 n\\ &= bn + 2d - c\log_2n' - c\log_2(n-n') + c \log_2 n\\ &= bn + 2d - c\log_2(n'(n-n')) + c \log_2 n\\ &= bn + 2d - c\log_2(\alpha n(n- \alpha n)) + c \log_2 n\\ &= bn + 2d - c\log_2(n^2 \alpha (1- \alpha )) + c \log_2 n\\ &= bn + 2d - 2c\log_2 n - c\log_2( \alpha (1- \alpha )) + c \log_2 n\\ &= 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)$$