Prove/Disprove asymptotics claims

60 Views Asked by At

Prove/Disprove:

$(1) \log((\sum _{k=1}^n(k^2))^3)= \mathcal{O}(n^2)$

$(2) \ 2^{n^3}=\mathcal{O}(3^{n^2})$

$(3) \ \forall f(n):f(n)=\mathcal{O}(\log n) \Rightarrow 2^{f(n)}=\mathcal{O}(n)$

$(4) \ \forall f(n):2^{f(n)}=\mathcal{O}(n) \Rightarrow f(n)=\mathcal{O}(\log n)$

My try:

$(1)$ is true.

$(2)$ is not true, but not sure how to prove it.

$(3)$ is not true.

$(4)$ is true.

Any help with $(2)$ appreciated.

1

There are 1 best solutions below

2
On BEST ANSWER

Note that $$2^{n^3}=2^{n^2\cdot n}=2^{2n^2}\cdot2^{n^2(n-2)}=4^{n^2}\cdot2^{n^2(n-2)}.$$ Can you finish?