0
$\begingroup$

I'm trying to solve an exercise from Introduction to Algorithms of Cormen - exrecise 4.3-3 on 3rd edition, which is 4.1-2 on 2nd edition.

Found a solution, which makes sense, but I don't understand one thing in it.

They write:

$$ c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{1}{c'}\right)-c'\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)\right) \geq $$ $$ \geq c'n\left(\lg{n}-2+\frac{1}{c'}-\frac{\lg(n-1)-1}{n}\right)$$

How did they transform the first line to the second line?

I tried to insert the right term expression into the left term parentheses, but got something else:

$$ c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{1}{c'}\right)-c'\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)\right) \geq $$

$$ \geq c'n\left(\lg{n}-\frac{\lg{n}}{n}+\frac{1}{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{\lg\left(\frac{n}{n-1}\right)}{n}+\frac{1}{c'}\right)=$$

$$ = c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{\lg\left(\frac{n}{n-1}\right)-\lg{n}+1}{n}+\frac{1}{c'}\right)=$$

$$ = c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

What am I missing here?

Can we say that $0<\frac{n}{n-1}<1$ and therefore $\lg(\frac{n}{n-1})<0$ ? And thus continue:

$$ \geq c'n\left(\lg{n}-1-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

Here I can claim that

$$ \lg(n-1)<n+1 \Rightarrow \frac{\lg(n-1)-1}{n}<1$$

If only I could have said $$ \frac{\lg(n-1)-1}{n}>0$$

(of course, I cannot say that...) But if I could - then I'm almost finished - return to our inequality:

$$ \geq c'n\left(\lg{n}-2+\frac{1}{c'}\right) \geq c'n\lg{n}$$

But, sadly, I've missed something over the lines.

Where am I wrong? How did the author of the solution that I have found did the transition?

EDIT

On another thought, I can prove that $$ \frac{\lg(n-1)-1}{n}>0$$

For big enough $n$, it's true that $\lg(n-1)>1$, therefore $ \frac{\lg(n-1)-1}{n}>0$

So, everything fits in.

Now my questions are: 1. Am I correct? 2. I still don't understand how to reach the suggested solution I've mentioned at the beginning of my answer.

EDIT 2

Well, when I read @fleablood 's answer, I realized that I made a stupid mistake. I should have written: $$1<\frac n{n-1} \le 2 \Rightarrow 0<\lg\left(\frac n{n-1}\right)\le1$$

And therefore, the transition from $$= c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right)$$

should be to

$$ \geq c'n\left(\lg{n}-2-\frac{\lg\left(n-1\right)-1}{n}+\frac{1}{c'}\right) $$

And that settles all my questions.

$\endgroup$
1
$\begingroup$

==== Now that I think of it I feel dumb ====

The key is $1 < \frac {n}{n-1} \le 2$ (equality holding if $n=2$) so

$0 < \log_2 \frac {n}{n-1}=\lg \frac {n}{n-1} \le 1$.

So $\lg{n}-1-\lg\left(\frac{n}{n-1} \right)\ge \lg{n} - 2$ and $\lg{n}-1-\lg(\frac{n}{n-1}) < \lg{n}-1$

so....

$c'n(\lg{n}-1-\lg(\frac{n}{n-1})+\frac{1}{c'})-c'(\lg{n}-1-\lg(\frac{n}{n-1})> c'n(\lg{n}-2+\frac{1}{c'})-c'(\lg{n}-1)$

(assuming $c'$ and $n$ are positive. I'm not sure why they didn't opt for a strict inequality.)

====old answer ====

$c'n\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)+\frac{1}{c'}\right)-c'\left(\lg{n}-1-\lg\left(\frac{n}{n-1}\right)\right) =$

$c'n\left(\lg{n}-2+\frac{1}{c'}\right)-c'\left(\lg{n}-1\right)+c'n-c'n\lg\left(\frac{n}{n-1}\right) +c'\lg\left(\frac{n}{n-1}\right)=$

$c'n\left(\lg{n}-2+\frac{1}{c'}-\frac{\lg(n-1)-1}{n}\right)+c'n-c'n\lg\left(\frac{n}{n-1}\right) +c'\lg\left(\frac{n}{n-1}\right)$

So (presuming $c', n > 0$ this is a matter of showing

$c'n-c'n\lg\left(\frac{n}{n-1}\right) +c'\lg\left(\frac{n}{n-1}\right)\ge 0$

[EDIT: D'oh. all values are positive so it is more than sufficient to prove $0 < \lg(\frac n{n-1}) \le 1$. Which it is if $1 < \frac n{n-1}=1+\frac 1{n-1} < $ base of $\lg$. Which is the case if base of $\lg \ge 2$. Presumably $\lg =\log_2$. My mistake was assuming NOTHING about the base until the very end putting off what should have been obvious from the start. Only at the end it became much more complicated.]

or $n + \lg(\frac n{n-1}) \ge n\lg(\frac n{n-1})$.

or $\lg (b^n\frac n{n-1}) \ge \lg ((\frac n{n-1})^n)$

or $b^n \ge (\frac n{n-1})^{n-1}$

Is $\lg = \log_2$?

If so... $1<\frac n{n-1} \le 2$ and $2^n \ge (\frac n{n-1})^n > (\frac n{n-1})^{n-1}$.

There's probably a more obvious way of "visually" seeing this ... but I'm missing it.

$\endgroup$
  • $\begingroup$ Well, now you've convinced me that they didn't made a mistake in the solution... But I find it hard to believe that they hid all this in that innocent-looking transition :( $\endgroup$ – Zvika Jun 21 '18 at 20:55
  • $\begingroup$ There's probably something I'm overlooking. What I did is easy but it's not do-it-in-your-head easy. $\endgroup$ – fleablood Jun 21 '18 at 21:53
  • 1
    $\begingroup$ Maybe it is.... If we assume $0 \le \lg n{n-1} < 1$ is do-it-in-your-head-easy (because $1 < \frac n{n-1} < 2$ is do-it-in-your-head-easy) then .... oh, for eff sake.... $\endgroup$ – fleablood Jun 21 '18 at 21:57
  • $\begingroup$ Great. Just note that you have a small typo in your last comment. Missing a \frac $\endgroup$ – Zvika Jun 22 '18 at 6:18
  • $\begingroup$ yeah... well, comments aren't editable. $\endgroup$ – fleablood Jun 22 '18 at 6:22

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.