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)

Question

I'm having a hard time finding the constants/witnesses $C_0$ and $k_0$ that show $(\log_b n)^c$ is $O(n^d)$. That is $|(\log_b n)^c| \leq C_0|n^d|$ for $n > k_0$ (b > 1, and c,d are positive).

I understand you can show just the Big-O relation through L-Hopital, but my specific issue is with finding the witnesses

For example, 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$, that is $C_0 = 1$ and $k_0 = 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)

Moreover, when I try to see the relation between say $(\log_2 x)^4$ and $x^2$, I see $x^2$ only seems to start exceeding $(\log_2 x)^4$ past x = 16 (via desmos again), i.e one pair of witnesses would be $C_0 = 1$ and $k_0 = 16$.

Hence I'm really lost in finding witness pairs for $(log_b n)^c \in O(n^d)$. Kindly please help suggest some strategies that would make it easier to solve.

---

I have a similar confusion for witnesses when showing:

1. $n^d \in O(b^n)$ ($b > 1$ and $d$ is positive)
2. $c^n \in O(n!)$ ($c > 1$)

But I can leave these 2 for a separate question. We can just focus on $(log_b n)^c \in O(n^d)$ in this thread.

---

Answer 1

For any pair of witness $(C_0, k_0)$, the pair of witness $(C_0, |k_0|)$ would work as well. So W.L.O.G we can only consider only the positive $k_0 > 0$, which gives us $$\begin{align*} (\log_b n)^c &\le C_0n^d & \forall n \ge k_0 \\ c \ln (\log_b n) &\le \ln C_0 + d \ln n & \forall n \ge k_0 \\ c \ln (\ln n) - c \ln (\ln b) - d \ln n &\le \ln C_0 & \forall n \ge k_0 \\ \end{align*}$$

Now take $h(x) = c \ln (\ln x) - c \ln (\ln b) - d \ln x$. We get $h'(x) = \frac{c}{x \ln x} - \frac{d}{x}$. This derivative $h'(x)$ will always be non-positive ($\le 0$) when $x > 1$ and $\frac{x\ln x}{x} \ge \frac{c}{d}$, or $x \ge e^{c/d}$. So for any $k_0 \ge e^{c/d}$, the value $h(x) : \forall x \ge k_0$ will be non-increasing. We can take the equality here $k_0 = e^{c/d}$, and let $C_0$ take care of the rest

Thus we only need to find the $C_0$ where $h(k_0) \le \ln C_0$, and as $h$ is non-increasing after that, it will never go above this value $\forall x \ge k_0$ $$\begin{align*} c \ln (\ln (e^{c/d})) - c \ln (\ln b) - d \ln (e^{c/d}) &\le \ln C_0 \\ \ln \left( \frac{\left( \frac{c}{d} \right)^c}{(\ln b)^c e^c} \right) &\le \ln C_0 \\ \left( \frac{c}{e d (\ln b)} \right)^c &\le C_0 \\ \left( \frac{c}{e d (\ln b)} \right)^c &= C_0 \\ \end{align*}$$