Mixing
How can I prove that $log^k(n) = O(n^epsilon)$?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
How can I prove that $log^k(n) = O(n^epsilon)$?
(for any $epsilon > 0 $ and for any integer and positive $k$).
I tried to do it by - definition , and to prove that exists $c,n_0 > 0$ so that for any $n > n_0 $ exists: $c cdot n^epsilon > log^k(n) $, but I don't have idea how to continue for this point.
I will be happy to listen ideas :).
calculus asymptotics
asked Jul 20 at 7:44
Software_t
1144
add a comment |Â
up vote
1
down vote
favorite
How can I prove that $log^k(n) = O(n^epsilon)$?
(for any $epsilon > 0 $ and for any integer and positive $k$).
I tried to do it by - definition , and to prove that exists $c,n_0 > 0$ so that for any $n > n_0 $ exists: $c cdot n^epsilon > log^k(n) $, but I don't have idea how to continue for this point.
I will be happy to listen ideas :).
calculus asymptotics
asked Jul 20 at 7:44
Software_t
1144
It's not only $O(n^ε)$, it's even $o(n^ε)$.
– Bernard
Jul 20 at 7:57
@Bernard Can you prove that please (that it's $o(n^epsilon)$)
– Software_t
Jul 20 at 8:04
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
How can I prove that $log^k(n) = O(n^epsilon)$?
(for any $epsilon > 0 $ and for any integer and positive $k$).
I tried to do it by - definition , and to prove that exists $c,n_0 > 0$ so that for any $n > n_0 $ exists: $c cdot n^epsilon > log^k(n) $, but I don't have idea how to continue for this point.
I will be happy to listen ideas :).
calculus asymptotics
asked Jul 20 at 7:44
Software_t
1144
How can I prove that $log^k(n) = O(n^epsilon)$?
(for any $epsilon > 0 $ and for any integer and positive $k$).
I tried to do it by - definition , and to prove that exists $c,n_0 > 0$ so that for any $n > n_0 $ exists: $c cdot n^epsilon > log^k(n) $, but I don't have idea how to continue for this point.
I will be happy to listen ideas :).
calculus asymptotics
asked Jul 20 at 7:44
Software_t
1144
edited Jul 20 at 7:49
user401938
asked Jul 20 at 7:44
Software_t
1144
asked Jul 20 at 7:44
Software_t
1144
asked Jul 20 at 7:44
Software_t
1144
1144
It's not only $O(n^ε)$, it's even $o(n^ε)$.
– Bernard
Jul 20 at 7:57
@Bernard Can you prove that please (that it's $o(n^epsilon)$)
– Software_t
Jul 20 at 8:04
add a comment |Â
It's not only $O(n^ε)$, it's even $o(n^ε)$.
– Bernard
Jul 20 at 7:57
@Bernard Can you prove that please (that it's $o(n^epsilon)$)
– Software_t
Jul 20 at 8:04
It's not only $O(n^ε)$, it's even $o(n^ε)$.
– Bernard
Jul 20 at 7:57
It's not only $O(n^ε)$, it's even $o(n^ε)$.
– Bernard
Jul 20 at 7:57
@Bernard Can you prove that please (that it's $o(n^epsilon)$)
– Software_t
Jul 20 at 8:04
@Bernard Can you prove that please (that it's $o(n^epsilon)$)
– Software_t
Jul 20 at 8:04
add a comment |Â
5 Answers
5
active
oldest
votes
up vote
0
down vote
accepted
By definition we have
$$log^k(n) = n^epsiloncdot fraclog^k(n)n^epsilon$$
with
$$fraclog^k(n)n^epsilonto 0$$
(refer to Evaluation $lim_nto inftyfraclog^k nn^epsilon$)
therefore
$$log^k(n) = o(n^epsilon)$$
answered Jul 20 at 8:07
gimusi
65.4k73584
1
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
 |Â
show 2 more comments
up vote
1
down vote
Consider $;logbiggl(dfraclog^knn^εbiggr)$:
$$logbiggl(dfraclog^knn^εbiggr)=klog(log n)-εlog n=-εlog nbiggl(1-frac kεunderbracefraclog(log n)log n_stackreldownarrow0biggr)$$
so the log tends to $-infty$ when $n$ tends to $infty$, i.e.
$$lim_ntoinftydfraclog^knn^ε=0ifflog^kn=o(n^ε),$$
and a fortiori, it is $:O(n^ε)$.
answered Jul 20 at 8:09
Bernard
110k635103
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
add a comment |Â
up vote
1
down vote
It is well known that $log (m)<m$ for all $m>0$. Taking $m=n^epsilon/k$ gives
$$dfracepsilonk log(n)<n^dfracepsilonk$$
and manipulating this equation gives
$$log^k (n)<left(frackepsilon right)^kn^epsilon. $$
edited Jul 28 at 8:36
Nosrati
19.5k41544
answered Jul 20 at 8:40
user1337
16.5k42989
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
add a comment |Â
up vote
0
down vote
Here we'll try to come up with an explicit lower bound for $n$ instead of using limits. We need to solve $log^k(n) leq n^epsilon$ (Here I assume the big-Oh constant $c=1$). Assuming $n$ large, in particular $n > 1$ we can rewrite $n = e^m$. for some $m > 0$. This gives us to solve:
$$
log^k(n) leq n^epsilon Leftrightarrow m^k leq e^epsilon m
$$
Now for $epsilon, m > 0$, we have
$$
e^epsilon m = sum_i=0^infty frac(epsilon m)^ii! > frac(epsilon m)^k+1(k+1)!
$$
This gives us the implication:
$$
m^k leq frac(epsilon m)^k+1(k+1)! implies m^k leq e^epsilon m
$$
Hence if we manage to solve for $m$ the LHS of the implication, we will have found a satisfying $m$ for the RHS and we will be done. Let's try:
$$
m^k leq frac(epsilon m)^k+1(k+1)! = fracepsilon^k+1(k+1)! m^k+1Leftrightarrow \
1 leq fracepsilon^k+1(k+1)! m Leftrightarrow \
frac(k+1)!epsilon^k+1 leq m
$$
By our definition we have $m = log(n)$, therefore we have the explicit (and awfully loose) bound:
$$
n geq expleft(frac(k+1)!epsilon^k+1right) implies log^k(n) leq n^epsilon
$$
(Note that I assume for simplicity that $c=1$. But it really doesn't matter. This shows that this proof can hold for any $c$, which means that we have the stronger result: $log^k(n) = o(n^epsilon)$)
answered Jul 20 at 8:05
Zubzub
3,8341921
add a comment |Â
up vote
0
down vote
Propositions 1. Function $f(x)=fracx^varepsilonln^kx$ is ascending for large $x>0$.
Because
$$f'(x)=fracx^varepsilon-1 (varepsilon ln^kx-k)ln^k+1x>0 iff
varepsilon ln^kx-k>0 iff
x> e^sqrt[k]frackvarepsilon$$
Propositions 2. $limlimits_xrightarrow inftyf(x) rightarrow infty$
If we assume it is bounded by a large $alpha>0, forall x>1$ and we know $lnx$ is ascending
$$fracx^varepsilonln^kx < alpha iff
1<x^varepsilon< alpha ln^kx iff
colorred0<varepsilon<fraclnalphalnx+fracklnlnxlnxrightarrow colorred0, xrightarrowinfty$$
which is a contradiction of $varepsilon>0$. So, $f(x)$ is increasing and has no upper bound.
As a result:
$$limlimits_nrightarrowinftyfracn^varepsilonln^knrightarrowinfty iff
limlimits_nrightarrowinftyfracln^knn^varepsilon=0 iff
ln^kn=oleft(n^varepsilonright)$$
answered Jul 20 at 8:31
rtybase
8,86721433
add a comment |Â
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
By definition we have
$$log^k(n) = n^epsiloncdot fraclog^k(n)n^epsilon$$
with
$$fraclog^k(n)n^epsilonto 0$$
(refer to Evaluation $lim_nto inftyfraclog^k nn^epsilon$)
therefore
$$log^k(n) = o(n^epsilon)$$
answered Jul 20 at 8:07
gimusi
65.4k73584
1
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
 |Â
show 2 more comments
up vote
0
down vote
accepted
By definition we have
$$log^k(n) = n^epsiloncdot fraclog^k(n)n^epsilon$$
with
$$fraclog^k(n)n^epsilonto 0$$
(refer to Evaluation $lim_nto inftyfraclog^k nn^epsilon$)
therefore
$$log^k(n) = o(n^epsilon)$$
answered Jul 20 at 8:07
gimusi
65.4k73584
1
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
 |Â
show 2 more comments
up vote
0
down vote
accepted
up vote
0
down vote
accepted
By definition we have
$$log^k(n) = n^epsiloncdot fraclog^k(n)n^epsilon$$
with
$$fraclog^k(n)n^epsilonto 0$$
(refer to Evaluation $lim_nto inftyfraclog^k nn^epsilon$)
therefore
$$log^k(n) = o(n^epsilon)$$
answered Jul 20 at 8:07
gimusi
65.4k73584
By definition we have
$$log^k(n) = n^epsiloncdot fraclog^k(n)n^epsilon$$
with
$$fraclog^k(n)n^epsilonto 0$$
(refer to Evaluation $lim_nto inftyfraclog^k nn^epsilon$)
therefore
$$log^k(n) = o(n^epsilon)$$
answered Jul 20 at 8:07
gimusi
65.4k73584
edited Jul 20 at 8:17
answered Jul 20 at 8:07
gimusi
65.4k73584
answered Jul 20 at 8:07
gimusi
65.4k73584
answered Jul 20 at 8:07
gimusi
65.4k73584
65.4k73584
1
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
 |Â
show 2 more comments
1
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
1
1
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
It's not clear to me. Why if $log^k(n) / n^epsilon -> 0 $ so it's say the conclusion you said?
– Software_t
Jul 20 at 8:09
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
@Software_t it's a standard limit, refer to math.stackexchange.com/q/1702483/505767
– gimusi
Jul 20 at 8:17
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
I know that. but ok, it's going to $0$ , how you get "therefore ..." ? ( $ n rightarrow infty $ )
– Software_t
Jul 20 at 8:19
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t Recall tha by definition $$f(x)=o(g(x)) iff f(x)=omega(x)cdot g(x)$$ with $omega(x)to 0$.
– gimusi
Jul 20 at 8:21
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
@Software_t In that case $g(x)$ is $n^epsilon$ and $omega(x)$ is $fraclog^k(n)n^epsilonto 0$.
– gimusi
Jul 20 at 8:23
 |Â
show 2 more comments
up vote
1
down vote
Consider $;logbiggl(dfraclog^knn^εbiggr)$:
$$logbiggl(dfraclog^knn^εbiggr)=klog(log n)-εlog n=-εlog nbiggl(1-frac kεunderbracefraclog(log n)log n_stackreldownarrow0biggr)$$
so the log tends to $-infty$ when $n$ tends to $infty$, i.e.
$$lim_ntoinftydfraclog^knn^ε=0ifflog^kn=o(n^ε),$$
and a fortiori, it is $:O(n^ε)$.
answered Jul 20 at 8:09
Bernard
110k635103
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
add a comment |Â
up vote
1
down vote
Consider $;logbiggl(dfraclog^knn^εbiggr)$:
$$logbiggl(dfraclog^knn^εbiggr)=klog(log n)-εlog n=-εlog nbiggl(1-frac kεunderbracefraclog(log n)log n_stackreldownarrow0biggr)$$
so the log tends to $-infty$ when $n$ tends to $infty$, i.e.
$$lim_ntoinftydfraclog^knn^ε=0ifflog^kn=o(n^ε),$$
and a fortiori, it is $:O(n^ε)$.
answered Jul 20 at 8:09
Bernard
110k635103
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Consider $;logbiggl(dfraclog^knn^εbiggr)$:
$$logbiggl(dfraclog^knn^εbiggr)=klog(log n)-εlog n=-εlog nbiggl(1-frac kεunderbracefraclog(log n)log n_stackreldownarrow0biggr)$$
so the log tends to $-infty$ when $n$ tends to $infty$, i.e.
$$lim_ntoinftydfraclog^knn^ε=0ifflog^kn=o(n^ε),$$
and a fortiori, it is $:O(n^ε)$.
answered Jul 20 at 8:09
Bernard
110k635103
Consider $;logbiggl(dfraclog^knn^εbiggr)$:
$$logbiggl(dfraclog^knn^εbiggr)=klog(log n)-εlog n=-εlog nbiggl(1-frac kεunderbracefraclog(log n)log n_stackreldownarrow0biggr)$$
so the log tends to $-infty$ when $n$ tends to $infty$, i.e.
$$lim_ntoinftydfraclog^knn^ε=0ifflog^kn=o(n^ε),$$
and a fortiori, it is $:O(n^ε)$.
answered Jul 20 at 8:09
Bernard
110k635103
answered Jul 20 at 8:09
Bernard
110k635103
answered Jul 20 at 8:09
Bernard
110k635103
answered Jul 20 at 8:09
Bernard
110k635103
110k635103
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
add a comment |Â
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
Can you explain please why if $;logbiggl(dfraclog^knn^εbiggr) rightarrow - infty $ , so $lim_ntoinftydfraclog^knn^ε=0 $ ?
– Software_t
Jul 20 at 8:16
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
You can look at the representative curve of the log, or simply take the inverse function: the exponential of this log tends to $0$.
– Bernard
Jul 20 at 8:30
add a comment |Â
up vote
1
down vote
It is well known that $log (m)<m$ for all $m>0$. Taking $m=n^epsilon/k$ gives
$$dfracepsilonk log(n)<n^dfracepsilonk$$
and manipulating this equation gives
$$log^k (n)<left(frackepsilon right)^kn^epsilon. $$
edited Jul 28 at 8:36
Nosrati
19.5k41544
answered Jul 20 at 8:40
user1337
16.5k42989
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
add a comment |Â
up vote
1
down vote
It is well known that $log (m)<m$ for all $m>0$. Taking $m=n^epsilon/k$ gives
$$dfracepsilonk log(n)<n^dfracepsilonk$$
and manipulating this equation gives
$$log^k (n)<left(frackepsilon right)^kn^epsilon. $$
edited Jul 28 at 8:36
Nosrati
19.5k41544
answered Jul 20 at 8:40
user1337
16.5k42989
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
add a comment |Â
up vote
1
down vote
up vote
1
down vote
It is well known that $log (m)<m$ for all $m>0$. Taking $m=n^epsilon/k$ gives
$$dfracepsilonk log(n)<n^dfracepsilonk$$
and manipulating this equation gives
$$log^k (n)<left(frackepsilon right)^kn^epsilon. $$
edited Jul 28 at 8:36
Nosrati
19.5k41544
answered Jul 20 at 8:40
user1337
16.5k42989
It is well known that $log (m)<m$ for all $m>0$. Taking $m=n^epsilon/k$ gives
$$dfracepsilonk log(n)<n^dfracepsilonk$$
and manipulating this equation gives
$$log^k (n)<left(frackepsilon right)^kn^epsilon. $$
edited Jul 28 at 8:36
Nosrati
19.5k41544
answered Jul 20 at 8:40
user1337
16.5k42989
edited Jul 28 at 8:36
Nosrati
19.5k41544
edited Jul 28 at 8:36
Nosrati
19.5k41544
edited Jul 28 at 8:36
Nosrati
19.5k41544
19.5k41544
answered Jul 20 at 8:40
user1337
16.5k42989
answered Jul 20 at 8:40
user1337
16.5k42989
answered Jul 20 at 8:40
user1337
16.5k42989
16.5k42989
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
add a comment |Â
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
@user108128 I think it does. Doesn't it?
– user1337
Jul 22 at 12:35
add a comment |Â
up vote
0
down vote
Here we'll try to come up with an explicit lower bound for $n$ instead of using limits. We need to solve $log^k(n) leq n^epsilon$ (Here I assume the big-Oh constant $c=1$). Assuming $n$ large, in particular $n > 1$ we can rewrite $n = e^m$. for some $m > 0$. This gives us to solve:
$$
log^k(n) leq n^epsilon Leftrightarrow m^k leq e^epsilon m
$$
Now for $epsilon, m > 0$, we have
$$
e^epsilon m = sum_i=0^infty frac(epsilon m)^ii! > frac(epsilon m)^k+1(k+1)!
$$
This gives us the implication:
$$
m^k leq frac(epsilon m)^k+1(k+1)! implies m^k leq e^epsilon m
$$
Hence if we manage to solve for $m$ the LHS of the implication, we will have found a satisfying $m$ for the RHS and we will be done. Let's try:
$$
m^k leq frac(epsilon m)^k+1(k+1)! = fracepsilon^k+1(k+1)! m^k+1Leftrightarrow \
1 leq fracepsilon^k+1(k+1)! m Leftrightarrow \
frac(k+1)!epsilon^k+1 leq m
$$
By our definition we have $m = log(n)$, therefore we have the explicit (and awfully loose) bound:
$$
n geq expleft(frac(k+1)!epsilon^k+1right) implies log^k(n) leq n^epsilon
$$
(Note that I assume for simplicity that $c=1$. But it really doesn't matter. This shows that this proof can hold for any $c$, which means that we have the stronger result: $log^k(n) = o(n^epsilon)$)
answered Jul 20 at 8:05
Zubzub
3,8341921
add a comment |Â
up vote
0
down vote
Here we'll try to come up with an explicit lower bound for $n$ instead of using limits. We need to solve $log^k(n) leq n^epsilon$ (Here I assume the big-Oh constant $c=1$). Assuming $n$ large, in particular $n > 1$ we can rewrite $n = e^m$. for some $m > 0$. This gives us to solve:
$$
log^k(n) leq n^epsilon Leftrightarrow m^k leq e^epsilon m
$$
Now for $epsilon, m > 0$, we have
$$
e^epsilon m = sum_i=0^infty frac(epsilon m)^ii! > frac(epsilon m)^k+1(k+1)!
$$
This gives us the implication:
$$
m^k leq frac(epsilon m)^k+1(k+1)! implies m^k leq e^epsilon m
$$
Hence if we manage to solve for $m$ the LHS of the implication, we will have found a satisfying $m$ for the RHS and we will be done. Let's try:
$$
m^k leq frac(epsilon m)^k+1(k+1)! = fracepsilon^k+1(k+1)! m^k+1Leftrightarrow \
1 leq fracepsilon^k+1(k+1)! m Leftrightarrow \
frac(k+1)!epsilon^k+1 leq m
$$
By our definition we have $m = log(n)$, therefore we have the explicit (and awfully loose) bound:
$$
n geq expleft(frac(k+1)!epsilon^k+1right) implies log^k(n) leq n^epsilon
$$
(Note that I assume for simplicity that $c=1$. But it really doesn't matter. This shows that this proof can hold for any $c$, which means that we have the stronger result: $log^k(n) = o(n^epsilon)$)
answered Jul 20 at 8:05
Zubzub
3,8341921
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Here we'll try to come up with an explicit lower bound for $n$ instead of using limits. We need to solve $log^k(n) leq n^epsilon$ (Here I assume the big-Oh constant $c=1$). Assuming $n$ large, in particular $n > 1$ we can rewrite $n = e^m$. for some $m > 0$. This gives us to solve:
$$
log^k(n) leq n^epsilon Leftrightarrow m^k leq e^epsilon m
$$
Now for $epsilon, m > 0$, we have
$$
e^epsilon m = sum_i=0^infty frac(epsilon m)^ii! > frac(epsilon m)^k+1(k+1)!
$$
This gives us the implication:
$$
m^k leq frac(epsilon m)^k+1(k+1)! implies m^k leq e^epsilon m
$$
Hence if we manage to solve for $m$ the LHS of the implication, we will have found a satisfying $m$ for the RHS and we will be done. Let's try:
$$
m^k leq frac(epsilon m)^k+1(k+1)! = fracepsilon^k+1(k+1)! m^k+1Leftrightarrow \
1 leq fracepsilon^k+1(k+1)! m Leftrightarrow \
frac(k+1)!epsilon^k+1 leq m
$$
By our definition we have $m = log(n)$, therefore we have the explicit (and awfully loose) bound:
$$
n geq expleft(frac(k+1)!epsilon^k+1right) implies log^k(n) leq n^epsilon
$$
(Note that I assume for simplicity that $c=1$. But it really doesn't matter. This shows that this proof can hold for any $c$, which means that we have the stronger result: $log^k(n) = o(n^epsilon)$)
answered Jul 20 at 8:05
Zubzub
3,8341921
Here we'll try to come up with an explicit lower bound for $n$ instead of using limits. We need to solve $log^k(n) leq n^epsilon$ (Here I assume the big-Oh constant $c=1$). Assuming $n$ large, in particular $n > 1$ we can rewrite $n = e^m$. for some $m > 0$. This gives us to solve:
$$
log^k(n) leq n^epsilon Leftrightarrow m^k leq e^epsilon m
$$
Now for $epsilon, m > 0$, we have
$$
e^epsilon m = sum_i=0^infty frac(epsilon m)^ii! > frac(epsilon m)^k+1(k+1)!
$$
This gives us the implication:
$$
m^k leq frac(epsilon m)^k+1(k+1)! implies m^k leq e^epsilon m
$$
Hence if we manage to solve for $m$ the LHS of the implication, we will have found a satisfying $m$ for the RHS and we will be done. Let's try:
$$
m^k leq frac(epsilon m)^k+1(k+1)! = fracepsilon^k+1(k+1)! m^k+1Leftrightarrow \
1 leq fracepsilon^k+1(k+1)! m Leftrightarrow \
frac(k+1)!epsilon^k+1 leq m
$$
By our definition we have $m = log(n)$, therefore we have the explicit (and awfully loose) bound:
$$
n geq expleft(frac(k+1)!epsilon^k+1right) implies log^k(n) leq n^epsilon
$$
(Note that I assume for simplicity that $c=1$. But it really doesn't matter. This shows that this proof can hold for any $c$, which means that we have the stronger result: $log^k(n) = o(n^epsilon)$)
answered Jul 20 at 8:05
Zubzub
3,8341921
edited Jul 20 at 8:13
answered Jul 20 at 8:05
Zubzub
3,8341921
answered Jul 20 at 8:05
Zubzub
3,8341921
answered Jul 20 at 8:05
Zubzub
3,8341921
3,8341921
add a comment |Â
add a comment |Â
up vote
0
down vote
Propositions 1. Function $f(x)=fracx^varepsilonln^kx$ is ascending for large $x>0$.
Because
$$f'(x)=fracx^varepsilon-1 (varepsilon ln^kx-k)ln^k+1x>0 iff
varepsilon ln^kx-k>0 iff
x> e^sqrt[k]frackvarepsilon$$
Propositions 2. $limlimits_xrightarrow inftyf(x) rightarrow infty$
If we assume it is bounded by a large $alpha>0, forall x>1$ and we know $lnx$ is ascending
$$fracx^varepsilonln^kx < alpha iff
1<x^varepsilon< alpha ln^kx iff
colorred0<varepsilon<fraclnalphalnx+fracklnlnxlnxrightarrow colorred0, xrightarrowinfty$$
which is a contradiction of $varepsilon>0$. So, $f(x)$ is increasing and has no upper bound.
As a result:
$$limlimits_nrightarrowinftyfracn^varepsilonln^knrightarrowinfty iff
limlimits_nrightarrowinftyfracln^knn^varepsilon=0 iff
ln^kn=oleft(n^varepsilonright)$$
answered Jul 20 at 8:31
rtybase
8,86721433
add a comment |Â
up vote
0
down vote
Propositions 1. Function $f(x)=fracx^varepsilonln^kx$ is ascending for large $x>0$.
Because
$$f'(x)=fracx^varepsilon-1 (varepsilon ln^kx-k)ln^k+1x>0 iff
varepsilon ln^kx-k>0 iff
x> e^sqrt[k]frackvarepsilon$$
Propositions 2. $limlimits_xrightarrow inftyf(x) rightarrow infty$
If we assume it is bounded by a large $alpha>0, forall x>1$ and we know $lnx$ is ascending
$$fracx^varepsilonln^kx < alpha iff
1<x^varepsilon< alpha ln^kx iff
colorred0<varepsilon<fraclnalphalnx+fracklnlnxlnxrightarrow colorred0, xrightarrowinfty$$
which is a contradiction of $varepsilon>0$. So, $f(x)$ is increasing and has no upper bound.
As a result:
$$limlimits_nrightarrowinftyfracn^varepsilonln^knrightarrowinfty iff
limlimits_nrightarrowinftyfracln^knn^varepsilon=0 iff
ln^kn=oleft(n^varepsilonright)$$
answered Jul 20 at 8:31
rtybase
8,86721433
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Propositions 1. Function $f(x)=fracx^varepsilonln^kx$ is ascending for large $x>0$.
Because
$$f'(x)=fracx^varepsilon-1 (varepsilon ln^kx-k)ln^k+1x>0 iff
varepsilon ln^kx-k>0 iff
x> e^sqrt[k]frackvarepsilon$$
Propositions 2. $limlimits_xrightarrow inftyf(x) rightarrow infty$
If we assume it is bounded by a large $alpha>0, forall x>1$ and we know $lnx$ is ascending
$$fracx^varepsilonln^kx < alpha iff
1<x^varepsilon< alpha ln^kx iff
colorred0<varepsilon<fraclnalphalnx+fracklnlnxlnxrightarrow colorred0, xrightarrowinfty$$
which is a contradiction of $varepsilon>0$. So, $f(x)$ is increasing and has no upper bound.
As a result:
$$limlimits_nrightarrowinftyfracn^varepsilonln^knrightarrowinfty iff
limlimits_nrightarrowinftyfracln^knn^varepsilon=0 iff
ln^kn=oleft(n^varepsilonright)$$
answered Jul 20 at 8:31
rtybase
8,86721433
Propositions 1. Function $f(x)=fracx^varepsilonln^kx$ is ascending for large $x>0$.
Because
$$f'(x)=fracx^varepsilon-1 (varepsilon ln^kx-k)ln^k+1x>0 iff
varepsilon ln^kx-k>0 iff
x> e^sqrt[k]frackvarepsilon$$
Propositions 2. $limlimits_xrightarrow inftyf(x) rightarrow infty$
If we assume it is bounded by a large $alpha>0, forall x>1$ and we know $lnx$ is ascending
$$fracx^varepsilonln^kx < alpha iff
1<x^varepsilon< alpha ln^kx iff
colorred0<varepsilon<fraclnalphalnx+fracklnlnxlnxrightarrow colorred0, xrightarrowinfty$$
which is a contradiction of $varepsilon>0$. So, $f(x)$ is increasing and has no upper bound.
As a result:
$$limlimits_nrightarrowinftyfracn^varepsilonln^knrightarrowinfty iff
limlimits_nrightarrowinftyfracln^knn^varepsilon=0 iff
ln^kn=oleft(n^varepsilonright)$$
answered Jul 20 at 8:31
rtybase
8,86721433
edited Jul 20 at 8:43
answered Jul 20 at 8:31
rtybase
8,86721433
answered Jul 20 at 8:31
rtybase
8,86721433
answered Jul 20 at 8:31
rtybase
8,86721433
8,86721433
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2857391%2fhow-can-i-prove-that-logkn-on-epsilon%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It's not only $O(n^ε)$, it's even $o(n^ε)$.
– Bernard
Jul 20 at 7:57
@Bernard Can you prove that please (that it's $o(n^epsilon)$)
– Software_t
Jul 20 at 8:04