1
$\begingroup$

I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$.

Here's my attempt: Suppose there is some $c>0$ and a positive integer $n_0$ such that $n_0 \le k < n \implies T(k) \ge ck \log_2 k$.

Then

$$\begin{eqnarray*} T(n) &=& 2T(\left \lfloor \frac{n}{2} \right \rfloor) + n \\ &\ge& 2c \left \lfloor \frac{n}{2} \right \rfloor \log_2 \left \lfloor \frac{n}{2} \right \rfloor + n \\ &\ge& 2c \left ( \frac{n - 1}{2} \right ) \log_2 \left ( \frac{n - 1}{2} \right ) + n \\ &=& c(n - 1) \log_2(n - 1) - c(n - 1) + n \\ &=& cn \log_2(n-1) - c \log_2(n-1) - c(n - 1) + n \\ &=& cn \log_2 \left [ n \left ( 1 - \frac{1}{n} \right ) \right ] - c \log_2(n-1) - c(n - 1) + n \\ &=& cn \log_2 n + cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n. \end{eqnarray*}$$

I can't determine if there is a $c > 0$ such that $cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$ is non-negative for $n$ large enough.

Also, I think this approach is too complicated given how easy it is to prove $T(n)=O(n \log_2 n)$. Am I missing some obvious estimate here?

Any help is welcome. Thanks.

$\endgroup$
2
  • $\begingroup$ "Suppose there is some $c>0$ and a positive integer $n_0$ such that $n_0 \le k < n \implies T(k) \ge ck \log_2 k$." What is $n$ here? $\endgroup$ – xskxzr Feb 22 '20 at 2:49
  • $\begingroup$ It's a positive integer for which I want to prove(by induction) the bound $T(n) \ge cn \log_2 n$. $\endgroup$ – Lázaro Albuquerque Feb 22 '20 at 4:14
1
$\begingroup$

$c=\frac{1}{2}$ is enough for large enough $n$.

Indeed, there are positive integers $n_1$ and $n_2$ such that

$$\begin{eqnarray*} n &\ge& n_1 \implies -\frac{1}{2} < \log_2 \left ( 1 - \frac{1}{n} \right ) \\ n &\ge& n_2 \implies -\frac{1}{2} < -\frac{1}{n} \log_2 (n - 1). \end{eqnarray*}$$

Rewriting $$cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$$

as

$$ cn \left [ \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c} \right ], $$

we have

$$n \ge \max(n_1, n_2) \implies -2 + \frac{1}{c} < \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c}.$$

But $-2 + \frac{1}{c} \ge 0 \iff c \le \frac{1}{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.