hosman
- 2
- 0
is log(n)^3 O(n^(1/3))??
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.
So the original question is stated as follows:
Q:Show that \log{n}^{3}=O(n^{1/3})
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?
Homework Statement
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.
Homework Equations
So the original question is stated as follows:
Q:Show that \log{n}^{3}=O(n^{1/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?