1
$\begingroup$

I have to solve this using the substitution method.

Floor functions cannot be skipped.


IH: Assume that $T(k) \geq ck\log(k) $ for all $k \leq n$, where c is a constant.

IS: Must prove $T(k) \geq ck\log(k) $

Proof:

\begin{align*} T(n) &= 2T(\left \lfloor{k/2}\right \rfloor ) + k\\ &\geq 2 c\left \lfloor{k/2}\right \rfloor\log(\left \lfloor{k/2}\right \rfloor) +k \end{align*}

We now have two cases: $k$ is even and $k$ is odd. It is easy to prove this case when $k$ is even, however I run into trouble when $k$ is odd.

When k is odd, $\lfloor k/2\rfloor = (k-1)/2$, which gives

\begin{align*} T(n)&\geq 2 c\tfrac{k-1}2\log(\tfrac{k-1}2) +k\\ &= c(k-1)\big(\log(k-1)-1\big) +k \qquad\qquad\text{(Since $\log2 = 1$)}\\ &= c\big(k\log (k-1) - k -\log(k-1) + 1\big) +k\\ &= ck\log (k-1) - ck -c\log(k-1) + c +k\\ &= ck\log k + ck\log\big(1-\tfrac{1}k\big) - ck -c\log(k-1) + c +k\,, \end{align*} where the last equality is because $\log(a-b) = \log\big(a\big(1-\tfrac{b}a\big)\big)$.

And here is where I am stuck. I have gotten the $ck\log k$, but cannot find the $c$ that will let me finish the problem.

Any help would be appreciated.

$\endgroup$
2
$\begingroup$

One way to go around the difficulties is as follows.

First, you prove that $T(n) = \Omega(n \log n)$ when $n = 2^k$.

Second, you prove that $T(n)$ is monotone (given monotone base cases).

Third, you finish the proof as follows. Let $m \leq n < 2m$, where $m = 2^k$. Then $$ T(n) \geq T(m) = \Omega(m \log m) = \Omega(n \log n). $$ Details left to you.

$\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.