# Proving $T(n) = T(n-2) + \log_2 n$ to be $\Omega(n\log_2 n)$

As title, for this recursive function $T(n) = T(n-2) + \log_2 n$, I worked out how to prove that it belongs to $O(n\log n)$; however I'm having trouble proving it to be also $\Omega(n\log n)$, i.e. lower-bounded by $n\log_2 n$ asymptotically.

Following the standard inductive procedure provided by CLRS algorithm text, I have: Assuming for some integer n such that for all $m<n$, $T(m) \geqq Cm\log_2m$, then:

$$T(n) \geqq C(n-2)\log_2(n-2) + \log_2 n$$

From this point on, it gets tricky (for me at least) to deduce the conclusion that $T(n) \geqq Cn\log_2n$

One possible way to move on is to give an observation that for all $n\geqq 4$, $\log_2(n-2)\geqq \log_2(n/2)=\log_2 n - 1$, but then this will generate a $-Cn$ term that I cannot get rid of.

The solutions manual of CLRS 2e suggests strengthening the induction hypothesis, i.e. assuming for all $m<n$, $T(m) \geqq Cm\log_2 m + Dm$ instead. It then arrives at $T(n) \geqq Cn\log_2 n$ and claims the proof is complete, which I think is incorrect as an inductive proof must arrive at exactly the same expression as the inductive hypothesis ($T(n) \geqq Cn\log_2 n + Dn$). In fact, I don't see how introducing a $Dm$ term here makes it easier at all to arrive at $T(n) \geqq Cn\log_2n + Dn$. I think I'm stuck. Any insight is much appreciated!

## 1 Answer

The recurrence relation is given as $T(n) = T(n-2) + \lg n$.

Let's unroll the formula half the way, that is, we will do $k = \lfloor n/4\rfloor$ steps

\begin{align} T(n) &= T(n-2) + \lg n \\ &= T(n-4) + \lg (n-2) + \lg n \\ &\ \ \vdots \\ &= T(n-2k-2) + \underbrace{\lg (n-2k) + \lg \big(n-2(k-1)\big) + \ldots + \lg (n-2\cdot0)}_{k \text{ summands, each }\geq\ \lg(n-2k)\ \simeq\ \lg(n/2)}\\ &\geq k\cdot \lg(n-2k). \end{align} Given that both $k$ and $n-2k$ are of order $\Theta(n)$, then $T(n)$ is bounded from below by $\Omega(n \log n)$.

I hope this helps $\ddot\smile$

• Wicked! Much appreciated! Could you elaborate a bit on how you came up with this method? – Naketo Mar 7 '16 at 11:03
• It's a standard trick and you can use it to get bounds as long the constant is actually a constant and its value doesn't matter. – dtldarek Mar 7 '16 at 12:57