A question on solution 6.1-2 from CLRS

[loop quantum gravity]

Homework Statement

How to prove the following claim?

that: $m=\lfloor \log_2 n \rfloor= \lfloor \lg n \rfloor$
from $n=2m+k−1$
?

Obviously we have $m=log_2(n−k+1)$
.
$k$ is the number of leaves.
My question has arisen from the solution here: https://walkccc.me/CLRS/Chap06/6.1/ of 6.1-2.

Thanks in advance!

Relevant Equations

maybe $\lfloor x \rfloor <x \le \rfloor x \lfloor +1$, not sure how or what to use to show their claim.

How to prove the following claim?

that: $$m=\lfloor \log_2 n \rfloor= \lfloor \lg n \rfloor$$
from $$n=2m+k−1$$
?

Obviously we have $$m=log_2(n−k+1)$$
.
$k$ is the number of leaves.
My question has arisen from the solution here: https://walkccc.me/CLRS/Chap06/6.1/ of 6.1-2.

Thanks in advance!

 

[anuttarasammyak]

A technical advice. Edit OP to replace single $ with double $ for proper Latex presentation, like

that: $$m=\lfloor \log_2 n \rfloor= \lfloor \lg n \rfloor$$
from $$n=2m+k−1$$.

You mean $2^m$ ?

 

[loop quantum gravity]

A technical adcvice. Edit to replace single $ with double $ for proper Latex presentation, like

that: $$m=\lfloor \log_2 n \rfloor= \lfloor \lg n \rfloor$$
from $$n=2m+k−1$$.

fixed that, thanks!

 

[pbuk]

fixed that, thanks!

Yes but you didn't fix this:

$$n=2m+k−1$$.

You mean $2^m$ ?

...although that is obviously what you mean if you have derived $m=\log_2(n−k+1)$.

Anyway you are looking at this the wrong way round: $m=\log_2(n−k+1)$ is not much help. Instead read the solution and consider how many elements there are in a heap of height $m=\lfloor \log_2 n \rfloor$.

 

[anuttarasammyak]

$$ 2^m < n < 2^{m+1}$$
Thus we expect
$$ 0 < k-1 < 2^m $$
I do not know what leaves are. does it have such a property ?