2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Wicked! Much appreciated! Could you elaborate a bit on how you came up with this method? $\endgroup$ – Naketo Mar 7 '16 at 11:03
  • $\begingroup$ 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. $\endgroup$ – dtldarek Mar 7 '16 at 12:57

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.