Showing that $\log{\log^d{3n}} = O(\log{\log^d{n}})$

Question

I'm trying to show this:

$$\log{\log^d{3n}} \leq q\cdot \log{\log^d{n}} \;\;\exists\, q,k > 0,\forall n>k, \text{where } d \text{ is a constant} > 0$$

This is what I have so far

$$\begin{align*}\log{\log^d{3n}} &\leq 2^d\log{\log^d{n}}\\ &\leq \log(({{\log^d{n})}^{2^d}})\end{align*}$$

I don't know if I'm on the right track since I'm stuck on showing that $\log^d{3n} < (\log^d{n})^{2^d}$.

Here log is $\log_2$, the base 2 logarithm.

Answer 1

$k=\max\{3,2^{\sqrt[d]{2}}\}$ is good enough for the job.

Then $\log^d(3n)<\log^d(n^2)= 2^d \log^d(n)$. Hence $\log(\log^d(3n))<\log(2^d \log^d(n)) = \log(\log^d(n))+\log(2^d) = \log(\log^d(n))+d$. Now let $q=d+1$. We have $\log(\log^d(n))>\log(\log^d(2^{\sqrt[d]{2}}))=\log(\sqrt[d]{2}^d)=\log(2)=1$. Hence $(d+1)\log(\log^d(n))>d+\log(\log^d(n))$.

---

Alternatively, use the following lemma:

For all $a,b>2$, $\log(ab)<(b+1)\log(a)$.

Proof: \begin{align*} \log(ab) &=\log(a)+\log(b) \\ &< \log(a)+b \\&= \log(a) + b\log(2) \\ &< \log(a) + b\log(a) = (b+1)\log(a) \end{align*}

This gives $\log(\log^d(3n))<\log((4\log(n))^d)=\log(4^d\log^d(n))<(4^d+1)\log(\log^d(n))$.