Also we know $d = log_2(n/2)$ rounded down to its nearest integer.
Add (-2) to each side $$d-1 <= log_2(n) - 2$$ $$d-1 <= log_2(n) - log_2(4)$$ $$d-1 <= log_2(n/4)$$
This is as far as I can get.
Asked
Active
Viewed 54 times
2 Answers
3
It is not necessarily true. For example, if $d=1$ and $n=1024$, then $$d+1=2\le 10=\log_2(n) $$ yet $$ d-1=0 \not > 7 = \log_2(n/8) $$
hmakholm left over Monica
- 286,031
-
OK, I've left out one piece of information. $d = log_2(n/2)$ rounded down to nearest integer. – kptlronyttcna Jun 19 '15 at 00:08
-
@kptlronyttcna: That's pretty critical. – hmakholm left over Monica Jun 19 '15 at 00:09
-
$d + 1 <= log_2(n)$ was actually derived from the missing info. I didn't noticed its importance after your answer. Sorry. – kptlronyttcna Jun 19 '15 at 00:15
1
If you take any real number $x$ and round down to the nearest integer, the result is greater than $x-1$. So $$d>\log_2\Bigl(\frac n2\Bigr)-1=\log_2n-2$$ and $$d-1>\log_2n-3=\log_2\Bigl(\frac n8\Bigr)\ .$$
David
- 82,662