3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you sure you understand what two-variable asymptotics are? See here and other posts linked from there for some thoughts. $\endgroup$ – Raphael May 7 '17 at 19:11
  • $\begingroup$ @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. $\endgroup$ – IllidanS4 wants Monica back May 7 '17 at 19:16
  • 1
    $\begingroup$ In which variable should the asymptotic be expressed then? (By the way, are you sure that "the smallest function" is well-defined?) $\endgroup$ – Raphael May 7 '17 at 19:22
1
$\begingroup$

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*} $$

$\endgroup$
2
$\begingroup$

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)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.