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:
- $n^d \in O(b^n)$ ($b > 1$ and $d$ is positive)
- $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.