Asymptotic notations involving log and binomial coefficients
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I'd like to ask for the hints for part (1) and (3) in the exercise below.
I stuck completely at part (1). For part (3), I found a way to simplify $f(n)/g(n)$, but then the answer would depend on the constant $k$, and not all the conclusions about the asymptotic relationships between $f$ and $g$ could be drawn from there. So I don't think my approach is correct. Here's my working so far:
Please note that we use the following definitions of the asymptotic notations:
$
$
asymptotics
asked Aug 10 at 23:22
ensbana
289113
add a comment |Â
up vote
0
down vote
favorite
I'd like to ask for the hints for part (1) and (3) in the exercise below.
I stuck completely at part (1). For part (3), I found a way to simplify $f(n)/g(n)$, but then the answer would depend on the constant $k$, and not all the conclusions about the asymptotic relationships between $f$ and $g$ could be drawn from there. So I don't think my approach is correct. Here's my working so far:
Please note that we use the following definitions of the asymptotic notations:
$
$
asymptotics
asked Aug 10 at 23:22
ensbana
289113
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'd like to ask for the hints for part (1) and (3) in the exercise below.
I stuck completely at part (1). For part (3), I found a way to simplify $f(n)/g(n)$, but then the answer would depend on the constant $k$, and not all the conclusions about the asymptotic relationships between $f$ and $g$ could be drawn from there. So I don't think my approach is correct. Here's my working so far:
Please note that we use the following definitions of the asymptotic notations:
$
$
asymptotics
asked Aug 10 at 23:22
ensbana
289113
I'd like to ask for the hints for part (1) and (3) in the exercise below.
I stuck completely at part (1). For part (3), I found a way to simplify $f(n)/g(n)$, but then the answer would depend on the constant $k$, and not all the conclusions about the asymptotic relationships between $f$ and $g$ could be drawn from there. So I don't think my approach is correct. Here's my working so far:
Please note that we use the following definitions of the asymptotic notations:
$
$
asymptotics
asked Aug 10 at 23:22
ensbana
289113
asked Aug 10 at 23:22
ensbana
289113
asked Aug 10 at 23:22
ensbana
289113
asked Aug 10 at 23:22
ensbana
289113
289113
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
I can try.
As for (1), note that $2^logx = x$.
Therefore,
beginalignn^1/log n & = 2^log(n^1/log n) \ & = 2^left( log n right) cdot left( 1/log n right) \ & = 2. endalign
So, $log n$ asymptotically dominates $n^1/log n$, as logarithms grow faster than constants.
As for (3), the "meaning" of big-theta, as it says, is that your function is bounded by two functions of equal asymptotic order. These two functions can differ by a constant factor.
answered Aug 11 at 1:15
Bladewood
305113
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I can try.
As for (1), note that $2^logx = x$.
Therefore,
beginalignn^1/log n & = 2^log(n^1/log n) \ & = 2^left( log n right) cdot left( 1/log n right) \ & = 2. endalign
So, $log n$ asymptotically dominates $n^1/log n$, as logarithms grow faster than constants.
As for (3), the "meaning" of big-theta, as it says, is that your function is bounded by two functions of equal asymptotic order. These two functions can differ by a constant factor.
answered Aug 11 at 1:15
Bladewood
305113
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
add a comment |Â
up vote
1
down vote
I can try.
As for (1), note that $2^logx = x$.
Therefore,
beginalignn^1/log n & = 2^log(n^1/log n) \ & = 2^left( log n right) cdot left( 1/log n right) \ & = 2. endalign
So, $log n$ asymptotically dominates $n^1/log n$, as logarithms grow faster than constants.
As for (3), the "meaning" of big-theta, as it says, is that your function is bounded by two functions of equal asymptotic order. These two functions can differ by a constant factor.
answered Aug 11 at 1:15
Bladewood
305113
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I can try.
As for (1), note that $2^logx = x$.
Therefore,
beginalignn^1/log n & = 2^log(n^1/log n) \ & = 2^left( log n right) cdot left( 1/log n right) \ & = 2. endalign
So, $log n$ asymptotically dominates $n^1/log n$, as logarithms grow faster than constants.
As for (3), the "meaning" of big-theta, as it says, is that your function is bounded by two functions of equal asymptotic order. These two functions can differ by a constant factor.
answered Aug 11 at 1:15
Bladewood
305113
I can try.
As for (1), note that $2^logx = x$.
Therefore,
beginalignn^1/log n & = 2^log(n^1/log n) \ & = 2^left( log n right) cdot left( 1/log n right) \ & = 2. endalign
So, $log n$ asymptotically dominates $n^1/log n$, as logarithms grow faster than constants.
As for (3), the "meaning" of big-theta, as it says, is that your function is bounded by two functions of equal asymptotic order. These two functions can differ by a constant factor.
answered Aug 11 at 1:15
Bladewood
305113
edited Aug 11 at 1:37
answered Aug 11 at 1:15
Bladewood
305113
answered Aug 11 at 1:15
Bladewood
305113
answered Aug 11 at 1:15
Bladewood
305113
305113
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
add a comment |Â
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^log_ad=d^log_ab$. I found this formula on wikipedia but don't know how to prove it. Could you clarify?
– ensbana
Aug 11 at 10:07
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
It's just the use of the definition of logarithms as the inverse (i.e. $log(2^x) = 2^logx = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($log_a (b^c) = c log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor.
– Bladewood
Aug 11 at 19:08
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%2f2878903%2fasymptotic-notations-involving-log-and-binomial-coefficients%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
