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$
  • $\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 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$ – lzralbu Feb 22 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}$.

| cite | improve this answer | |
$\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.