1
$\begingroup$

In Rosen's discrete Math textbook, they mention in the solutions for one problem that $(\log_2 x)^4 \leq x^3$ for $x > 1$. However, I'm not sure how to exactly derive that myself, nor does the textbook give an explanation as to how it got that answer. I can only see that it makes sense via desmos (at least for the finite amount of points it shows lol).

Yesterday I had asked about a general way of finding a pair of witnesses/constants ($C_0$ and $k_0$) when showing $(log_b n)^c$ is $O(n^d)$ (b > 1 and c, d are positive): Determining the witnesses (constants $C_0$ and $k_0$) when showing $(log_b n)^c$ is $O(n^d)$ (b > 1 and c,d are positive)

I did get that one possible witness pair is that $C_{0}=\left(\frac{c}{ed\ln\left(b\right)}\right)^{c}$ and $k_{0}=e^{\frac{c}{d}}$, but that only tells me that $(\log_2 x)^4 \leq 0.250769765966x^3$ for $x > 3.79366789468$. Hence I'm still stuck on showing $(\log_2 x)^4 \leq x^3$ for $x > 1$ (new question, not duplicate lol)

Kindly please help me.

$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

We have that by $x=2^y$ with $y>0$

$$(\log_2 x)^4 \leq x^3 \iff y^4 \leq 8^y \iff \frac{\log y}{y}\le \frac{3\log 2}{4}$$

which is true since $\frac{\log y}{y}$ reaches its maximum at $y=e$.

$\endgroup$
12
  • $\begingroup$ Awesome! Just one small question. How'd you show $\frac{\log_2 e}{e} \leq \frac{3}{4}$ without calculator? $\endgroup$
    – Bob Marley
    Commented Jun 28 at 16:50
  • $\begingroup$ We can use that $\frac1e< \frac38< \frac{3\log 2}{4}$ $\endgroup$
    – user
    Commented Jun 28 at 16:58
  • 1
    $\begingroup$ Indeed $8<3e$ and $\frac 3 8<\frac{3\log 4}8=\frac{3\log 2}4$. $\endgroup$
    – user
    Commented Jun 28 at 17:21
  • $\begingroup$ this strategy is pretty cool since I just used it to determine for which k such that x > k satisfies $(\log_2 x)^4 \leq x$. This means $x > 2^{\log_2 k}$, hence if $x = 2^y$, then $y > \log_2 k$. $y^4 \leq 2^y \iff \frac{\log_2 y}{y} \leq \frac{1}{4}$. Through trial and error I got $y = 16 \to \frac{\log_2 y}{y} = 1/4$, and since derivative is $< 0$ for $y > e$ and $16 > e$, our main inequality is satisfied for all $y \geq 16$, meaning $x = 2^y \geq 2^{16}$, hence k can be $2^{16}$. Moreover if $y$ is strictly greater than 16, then $\frac{\log_2 y}{y} < \frac{1}{4}$ (strictly)... $\endgroup$
    – Bob Marley
    Commented Jun 28 at 17:28
  • $\begingroup$ ...hence for $x > 2^{16}$, we get $(\log_2 x)^4 < x$ (strictly). Now I'm trying to figure out a more deterministic way of finding the y that makes the inequality work out. You have any ideas? :) $\endgroup$
    – Bob Marley
    Commented Jun 28 at 17:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .