# Is log(n)^3 O(n^(1/3))?

1. Feb 8, 2009

### hosman

is log(n)^3 O(n^(1/3))??

1. The problem statement, all variables and given/known data

So the problem has to do with big o notation, I came up with a solution but I think even in this summed up solution I give I am making too much assumptions or that it is just plainly wrong, if it is please let me know.

2. Relevant equations

So the original question is stated as follows:

Q:Show that $$\log{n}^{3}=O(n^{1/3})$$

3. The attempt at a solution

My basic idea was to use the derivative of the third root of both functions and prove that $$n^{1/9}$$ will have the greater one of the two and thus at some point the two functions will be equal and then $$n^{1/9}$$ will become greater allowing $$\log{n}$$ to have a order complexity of $$n^{1/9}$$,
which implies $$\log{n}^{3}=O(n^{1/3})$$

so here it is:
if $$n^{1/3}$$ has $$O(n^{1/3})$$ the so should...
$$\sqrt[3]{n^{1/3}}$$ have $$O\left(\sqrt[3]{n^{1/3}}\right)$$
and so I take the derivative of the third root (to simplify problem) of these functions and get:

$$\frac{d}{dn}\left(\log{n}\right)=\frac{1}{n\ln{10}}$$

$$\frac{d}{dn}\left(n^{1/9}\right)=\frac{1}{9n^{8/9}}$$

clearly $$\frac{1}{n}<\frac{1}{n^{8/9}}$$ for big values of n.

thus the derivative of $$n^{1/9}$$ will eventually become greater than $$\log{n}}$$ and this means (leaving out the actual calculation of following constants):

$$\exists N,c\in\Re$$ such that $$\forall n \geq N$$

$$\log{n} \leq c\left(n^{1/9}\right)$$ so that (skipping some more steps..)

$$\log{n}^{3}=O(n^{1/3})$$

for the sake of brevity I am leaving out steps but I think that the solution still makes sense?

2. Feb 9, 2009

### hosman

Re: is log(n)^3 O(n^(1/3))??

I just found out that the actual problem is litte o not big O so its
Q: proof (logn)^3 is o(n^(1/3))

hmmmmm....