Prove or disprove: $(\ln n)^2 \in O(\ln(n^2)).$

Question

Prove or disprove: $(\ln n)^2 \in O(\ln(n^2)).$

I think I would start with expanding the left side. How would I go about this?

score 2 · Answer 1 · answered Dec 10 '15 at 17:23

2

Here are two hints:

$O(\ln(n^2)) = O(2 \ln n) = O(\ln n)$
$x^2 \notin O(x)$

Can you finish from here?

answered Dec 10 '15 at 17:23

score 2 · Answer 2 · answered Dec 10 '15 at 17:23

2

Notice that: $$\forall n\in\mathbb{N}_{\geqslant 1},\ln\left(n^2\right)=2\ln(n).$$ Hence, one gets: $$O\left(\ln\left(n^2\right)\right)=O(\ln(n)).$$ Now, do you think $\ln(n)^2=O(\ln(n))$ i.e. is $(\ln(n))$ bounded?

answered Dec 10 '15 at 17:23

C. Falcon

19,042

Prove or disprove: $(\ln n)^2 \in O(\ln(n^2)).$

2 Answers2