# How do you prove that the recurrence $T(n) = 2T(\lfloor{n/2}\rfloor) + n$ is $\Omega(n \lg n)$?

I'm working through CLRS (Introduction to Algorithms, 3rd edition) and I'm in the section about using the "substitution method" and induction to prove asymptotic bounds for recurrences. I'm trying to solve this problem (4.3-3) and am running into problems dealing with the floor function.

Show that $$T(n) = 2T(\lfloor{n/2}\rfloor) + n$$ is $$\Omega(n \lg n)$$

This was my original attempt for the substitution step, and I also see this published online in a non-official solution guide:

\begin{align} T(n) &\ge 2c\lfloor n/2 \rfloor \lg (\lfloor n/2 \rfloor) + n\\ &\ge cn \lg (n/2) + n\\ &= cn \lg n - c n \lg 2 + n\\ &= cn \lg n \quad \text{if} \space c \le 1 \end{align}

But removing the floor functions directly between lines 1 and 2 seems like it could invalidate the inequality. I found another solution guide that gets around this by substituting $$n/4$$ for $$\lfloor n/2 \rfloor$$ but ends with this, which also seems to invalidate the inequality:

\begin{align} T(n) &\ge c(n/2)\lg n - cn + n\\ &\ge cn \lg n \quad \text{if} \space c \le 1 \end{align} This also doesn't seem to hold, for example, if $$c = 1$$. Are these approaches both just wrong or am I missing something? What's the best way to deal with the floor division in this problem?

Yes, the two solutions are not so strict as you found. I'll give my solution: \begin{aligned} T\left( n \right) &\ge 2c\lfloor n/2 \rfloor \lg \left( \lfloor n/2 \rfloor \right) +n\\ &\ge c\left( n-2 \right) \lg \left( \left( n-2 \right) /2 \right) +n\\ &=cn\lg \left( \left( n-2 \right) /2 \right) -2c\lg \left( \left( n-2 \right) /2 \right) +n\\ &=cn\lg \left( n-2 \right) -2cn\lg 2-2c\lg \left( n-2 \right) +2c\lg 2+n\\ &=c\left( n-2 \right) \lg \left( n-2 \right) +2\lg \left( n-2 \right) -2cn\lg 2-2c\lg \left( n-2 \right) +2c\lg 2+n\\ &\geq c\left( n-2 \right) \lg \left( n-2 \right)\\ &=\Omega(n \lg n) \end{aligned} Since $$\underset{n\to \infty }{\text{lim}}\frac{c (n-2) \lg (n-2)}{n \lg n} = c>0$$

$$c\left( n-2 \right) \lg \left( n-2 \right)=\Omega(n \lg n)$$ is true from the definition of $$\Omega$$: $$\text{if }{\displaystyle \liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0}, \text{then } f(n)=\Omega (g(n))$$

• I don't think I understand how you get from line 3 to line 4—how does the second term include a 2? Dec 19 '20 at 22:05

You want to show that there is some $$c>0$$ such that for all $$n$$ large enough $$T(n) \geqslant cn\lg n$$.
I present here a hopefully intuitive inductive approach. We will first check how the inductive step goes.

Suppose that for some $$k\geqslant 1$$ we have $$T(k)\geqslant ck\lg k$$.
Can we show that this relation also holds for some other (greater) values $$n$$?
If we follow the recursive definition of $$T$$, we'll see that $$T(2k)$$ and $$T(2k+1)$$ can both be expressed in terms of $$T(k)$$.

First, consider the case $$n = 2k$$. Then $$T(n) = 2T(k) + 2k$$ and we'll have $$T(n) \geqslant c(2k)\lg(k) + 2k$$.

It's easy to check that $$c\leqslant 1$$ implies $$c(2k)\lg(k)+2k \geqslant c(2k)\lg(2k)$$, regardless of the value of $$k$$. In this case, $$T(n)\geqslant cn\lg n$$ as desired.

Now, consider the case $$n = 2k+1$$. Then $$T(n) = 2T(k) + 2k + 1$$ and we'll have $$T(n)\geqslant c(2k)\lg(k)+(2k+1)$$. Under what conditions on $$c$$ do we have

$$c(2k)\lg(k)+(2k+1) \geqslant c(2k+1)\lg(2k+1)\,\,?$$

That is equivalent to

$$c\leqslant \frac{2k+1}{(2k+1)\lg(2k+1)-2k\lg(k)}.$$

You only really need this to be $$\geqslant \epsilon>0$$ as $$k\to\infty$$, and it's easy to show that. For instance, you could show that the RHS converges to $$1$$ as $$k\to\infty$$.

That said, you could also show that the minimum is attained at $$k=1$$ $$($$with value $$\log 2/\log 3\approx 0.63 < 1)$$, and this will save us some work in the end with base cases by allowing us to consider base cases right from the get go ($$k=1$$).

We hence conclude that $$c\leqslant \log 2/\log 3$$ implies $$T(2k+1) \geqslant c(2k+1)\lg(2k+1)$$, or $$T(n)\geqslant cn\lg n$$, once again regardless of the value of $$k$$.

Combining both cases, we conclude that for $$c\leqslant \log 2/\log 3$$, $$T(k)\geqslant ck\lg k$$ implies that both $$T(2k)\geqslant c(2k)\lg(2k)$$ and $$T(2k + 1)\geqslant c(2k + 1)\lg(2k + 1)$$.
This will be our inductive step.

To complete the induction, we must now handle the base cases. Our inductive step shows that the relation can be propagated forward from a base case, but not in the traditional way (from $$n$$ to $$n+1$$). Rather, our inductive step is a sort of doubling ($$n$$ to $$2n$$ and $$2n+1$$), which in general leaves gaps.

Indeed, for the sake of example, suppose we took a single base case of $$k = 7$$. Our inductive step would propagate the relation to $$n\in\{14, 15\}$$, and from these we'd get $$n\in\{28,29,30,31\}$$, and so on and so forth. It's easy to see that we'd miss many values.

We need a modified induction for our modified inductive step.

Lemma (Modified induction): Let $$P(n)$$ be some proposition about $$n$$.
Suppose that if $$P(n)$$ is true, then $$P(2n)$$ and $$P(2n+1)$$ are also true.
Additionally, suppose that there is some $$j\geqslant 0$$, such that $$P(n)$$ is true for all $$n$$ with $$2^j\leqslant n <2^{j+1}$$.

Then $$P(n)$$ is true for all $$n\geqslant 2^j$$.

Once you've proved the lemma, we can finish the exercise. If we take $$j=0$$ in the lemma, we'd need only show that $$P(1)$$ is true. And indeed, it is.

We can calculate the first few values of $$T$$ by hand: $$T(0) = 0$$ and $$T(1) = 1$$. The proposition $$P(1)$$ is then $$T(1) = 1 \geqslant c\lg 1 = 0$$, which is obviously true and concludes the induction.

This approach also helps show where tightness was lacking in the answers provided. Looser values of $$c$$ (meaning values closer to $$1$$) will require larger values of $$k$$ in order for the inductive step $$k\mapsto 2k+1$$ to work.
And, indeed, for $$c\geqslant 1$$ (including $$c=1$$) the inductive step does not hold for any $$k$$.

• Thank you, this is very helpful. I hadn't considered proving two separate induction steps for $2k$ and $2k+1$ instead of proving one step with a floor function. It makes the algebra much easier to understand. Dec 19 '20 at 22:03