Mixing
Big-$O$ of $ log binom{n}{n/2} $
$begingroup$
I'm asked to evaluate this: $ mathcal{O} bigg( log_2 binom{n}{n/2} bigg) $.
I played with this a bit and I keep getting $mathcal{O} (nlog n)$.
When I substitute $n! = sqrt{2pi n} Big(dfrac{n}{e}Big)^n $ I get $mathcal{O}(n)$, which is the correct answer.
Can you please tell me how to do it without using the above substitution?
asymptotics computational-complexity
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
$endgroup$
add a comment |
$begingroup$
I'm asked to evaluate this: $ mathcal{O} bigg( log_2 binom{n}{n/2} bigg) $.
I played with this a bit and I keep getting $mathcal{O} (nlog n)$.
When I substitute $n! = sqrt{2pi n} Big(dfrac{n}{e}Big)^n $ I get $mathcal{O}(n)$, which is the correct answer.
Can you please tell me how to do it without using the above substitution?
asymptotics computational-complexity
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
$endgroup$
$begingroup$
Is your goal to make the "substitution" rigorous (e.g. using the precise statement of Stirling's approximation), or to do it without using Stirling at all?
$endgroup$
– Nate Eldredge
Jan 18 at 22:16
2
$begingroup$
You can also use the majoration of $binom{n}{n/2}$ by $2^n$ (this is the sum of the $binom{n}{k} $).
$endgroup$
– DLeMeur
Jan 18 at 22:46
$begingroup$
@NateEldredge without using Stirling. Stirling's formula is only an approximation, right? Is there any straightforward way to prove it?
$endgroup$
– Altun Hasanli
Jan 19 at 9:50
$begingroup$
@AltunHasanli: Well, it is an approximation, but there are theorems about how large the error in the approximation might be. Wikipedia has lots of results and references.
$endgroup$
– Nate Eldredge
Jan 19 at 15:37
add a comment |
$begingroup$
I'm asked to evaluate this: $ mathcal{O} bigg( log_2 binom{n}{n/2} bigg) $.
I played with this a bit and I keep getting $mathcal{O} (nlog n)$.
When I substitute $n! = sqrt{2pi n} Big(dfrac{n}{e}Big)^n $ I get $mathcal{O}(n)$, which is the correct answer.
Can you please tell me how to do it without using the above substitution?
asymptotics computational-complexity
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
$endgroup$
I'm asked to evaluate this: $ mathcal{O} bigg( log_2 binom{n}{n/2} bigg) $.
I played with this a bit and I keep getting $mathcal{O} (nlog n)$.
When I substitute $n! = sqrt{2pi n} Big(dfrac{n}{e}Big)^n $ I get $mathcal{O}(n)$, which is the correct answer.
Can you please tell me how to do it without using the above substitution?
asymptotics computational-complexity
asymptotics computational-complexity
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
asked Jan 18 at 22:00
Altun HasanliAltun Hasanli
233
233
$begingroup$
Is your goal to make the "substitution" rigorous (e.g. using the precise statement of Stirling's approximation), or to do it without using Stirling at all?
$endgroup$
– Nate Eldredge
Jan 18 at 22:16
2
$begingroup$
You can also use the majoration of $binom{n}{n/2}$ by $2^n$ (this is the sum of the $binom{n}{k} $).
$endgroup$
– DLeMeur
Jan 18 at 22:46
$begingroup$
@NateEldredge without using Stirling. Stirling's formula is only an approximation, right? Is there any straightforward way to prove it?
$endgroup$
– Altun Hasanli
Jan 19 at 9:50
$begingroup$
@AltunHasanli: Well, it is an approximation, but there are theorems about how large the error in the approximation might be. Wikipedia has lots of results and references.
$endgroup$
– Nate Eldredge
Jan 19 at 15:37
add a comment |
$begingroup$
Is your goal to make the "substitution" rigorous (e.g. using the precise statement of Stirling's approximation), or to do it without using Stirling at all?
$endgroup$
– Nate Eldredge
Jan 18 at 22:16
2
$begingroup$
You can also use the majoration of $binom{n}{n/2}$ by $2^n$ (this is the sum of the $binom{n}{k} $).
$endgroup$
– DLeMeur
Jan 18 at 22:46
$begingroup$
@NateEldredge without using Stirling. Stirling's formula is only an approximation, right? Is there any straightforward way to prove it?
$endgroup$
– Altun Hasanli
Jan 19 at 9:50
$begingroup$
@AltunHasanli: Well, it is an approximation, but there are theorems about how large the error in the approximation might be. Wikipedia has lots of results and references.
$endgroup$
– Nate Eldredge
Jan 19 at 15:37
$begingroup$
Is your goal to make the "substitution" rigorous (e.g. using the precise statement of Stirling's approximation), or to do it without using Stirling at all?
$endgroup$
– Nate Eldredge
Jan 18 at 22:16
$begingroup$
Is your goal to make the "substitution" rigorous (e.g. using the precise statement of Stirling's approximation), or to do it without using Stirling at all?
$endgroup$
– Nate Eldredge
Jan 18 at 22:16
2
2
$begingroup$
You can also use the majoration of $binom{n}{n/2}$ by $2^n$ (this is the sum of the $binom{n}{k} $).
$endgroup$
– DLeMeur
Jan 18 at 22:46
$begingroup$
You can also use the majoration of $binom{n}{n/2}$ by $2^n$ (this is the sum of the $binom{n}{k} $).
$endgroup$
– DLeMeur
Jan 18 at 22:46
$begingroup$
@NateEldredge without using Stirling. Stirling's formula is only an approximation, right? Is there any straightforward way to prove it?
$endgroup$
– Altun Hasanli
Jan 19 at 9:50
$begingroup$
@NateEldredge without using Stirling. Stirling's formula is only an approximation, right? Is there any straightforward way to prove it?
$endgroup$
– Altun Hasanli
Jan 19 at 9:50
$begingroup$
@AltunHasanli: Well, it is an approximation, but there are theorems about how large the error in the approximation might be. Wikipedia has lots of results and references.
$endgroup$
– Nate Eldredge
Jan 19 at 15:37
$begingroup$
@AltunHasanli: Well, it is an approximation, but there are theorems about how large the error in the approximation might be. Wikipedia has lots of results and references.
$endgroup$
– Nate Eldredge
Jan 19 at 15:37
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I assume that $n=2k$.
Note that $log_2binom{n}{n/2}=Oleft(logbinom{n}{n/2}right)$ by the change-of-base formula for logarithms. Thus, we just need to show that $$logbinom{n}{n/2}=O(n).$$ Using Riemann-Stieltjes integration, we can show that $$log(n!)=sum_{j=1}^nlog(j)=nlog n-n+O(log n).tag{1}$$
This is actually stronger than what we need; we only need that $log(n!)=nlog n+O(n)$. As such, we'll use the weaker statement in what follows.
Using $(1)$, the definition of the binomial, and the property of logarithms that $log(a/b)=log(a)-log(b)$, we can show that for $n=2k$, $$logbinom{n}{n/2}=logleft(frac{(2k)!}{(k!)^2}right)=2klog(2k)-2klog(k)+O(k)=O(n).$$
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
$endgroup$
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078805%2fbig-o-of-log-binomnn-2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I assume that $n=2k$.
Note that $log_2binom{n}{n/2}=Oleft(logbinom{n}{n/2}right)$ by the change-of-base formula for logarithms. Thus, we just need to show that $$logbinom{n}{n/2}=O(n).$$ Using Riemann-Stieltjes integration, we can show that $$log(n!)=sum_{j=1}^nlog(j)=nlog n-n+O(log n).tag{1}$$
This is actually stronger than what we need; we only need that $log(n!)=nlog n+O(n)$. As such, we'll use the weaker statement in what follows.
Using $(1)$, the definition of the binomial, and the property of logarithms that $log(a/b)=log(a)-log(b)$, we can show that for $n=2k$, $$logbinom{n}{n/2}=logleft(frac{(2k)!}{(k!)^2}right)=2klog(2k)-2klog(k)+O(k)=O(n).$$
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
$endgroup$
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
|
show 1 more comment
$begingroup$
I assume that $n=2k$.
Note that $log_2binom{n}{n/2}=Oleft(logbinom{n}{n/2}right)$ by the change-of-base formula for logarithms. Thus, we just need to show that $$logbinom{n}{n/2}=O(n).$$ Using Riemann-Stieltjes integration, we can show that $$log(n!)=sum_{j=1}^nlog(j)=nlog n-n+O(log n).tag{1}$$
This is actually stronger than what we need; we only need that $log(n!)=nlog n+O(n)$. As such, we'll use the weaker statement in what follows.
Using $(1)$, the definition of the binomial, and the property of logarithms that $log(a/b)=log(a)-log(b)$, we can show that for $n=2k$, $$logbinom{n}{n/2}=logleft(frac{(2k)!}{(k!)^2}right)=2klog(2k)-2klog(k)+O(k)=O(n).$$
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
$endgroup$
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
|
show 1 more comment
$begingroup$
I assume that $n=2k$.
Note that $log_2binom{n}{n/2}=Oleft(logbinom{n}{n/2}right)$ by the change-of-base formula for logarithms. Thus, we just need to show that $$logbinom{n}{n/2}=O(n).$$ Using Riemann-Stieltjes integration, we can show that $$log(n!)=sum_{j=1}^nlog(j)=nlog n-n+O(log n).tag{1}$$
This is actually stronger than what we need; we only need that $log(n!)=nlog n+O(n)$. As such, we'll use the weaker statement in what follows.
Using $(1)$, the definition of the binomial, and the property of logarithms that $log(a/b)=log(a)-log(b)$, we can show that for $n=2k$, $$logbinom{n}{n/2}=logleft(frac{(2k)!}{(k!)^2}right)=2klog(2k)-2klog(k)+O(k)=O(n).$$
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
$endgroup$
I assume that $n=2k$.
Note that $log_2binom{n}{n/2}=Oleft(logbinom{n}{n/2}right)$ by the change-of-base formula for logarithms. Thus, we just need to show that $$logbinom{n}{n/2}=O(n).$$ Using Riemann-Stieltjes integration, we can show that $$log(n!)=sum_{j=1}^nlog(j)=nlog n-n+O(log n).tag{1}$$
This is actually stronger than what we need; we only need that $log(n!)=nlog n+O(n)$. As such, we'll use the weaker statement in what follows.
Using $(1)$, the definition of the binomial, and the property of logarithms that $log(a/b)=log(a)-log(b)$, we can show that for $n=2k$, $$logbinom{n}{n/2}=logleft(frac{(2k)!}{(k!)^2}right)=2klog(2k)-2klog(k)+O(k)=O(n).$$
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
answered Jan 19 at 4:20
ClaytonClayton
19.2k33286
19.2k33286
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
|
show 1 more comment
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Is Big-O of $log binom{n}{n/2} $ the same as Big-Theta of $log binom{n}{n/2} $ ????
$endgroup$
– Altun Hasanli
Jan 19 at 20:46
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
Sorry, I’m not familiar with $Theta(f(x))$ notation. Can you tell me the definition?
$endgroup$
– Clayton
Jan 19 at 20:51
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
why do we ignore $n log n$ in line 1 ? I don't understand
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
khanacademy.org/computing/computer-science/algorithms/…
$endgroup$
– Altun Hasanli
Jan 19 at 20:53
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
$begingroup$
@Altun we aren’t ignoring anything. It is precisely that asymptotic that allows you to deduce the desired bound.
$endgroup$
– Clayton
Jan 19 at 23:18
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3078805%2fbig-o-of-log-binomnn-2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Is your goal to make the "substitution" rigorous (e.g. using the precise statement of Stirling's approximation), or to do it without using Stirling at all?
$endgroup$
– Nate Eldredge
Jan 18 at 22:16
2
$begingroup$
You can also use the majoration of $binom{n}{n/2}$ by $2^n$ (this is the sum of the $binom{n}{k} $).
$endgroup$
– DLeMeur
Jan 18 at 22:46
$begingroup$
@NateEldredge without using Stirling. Stirling's formula is only an approximation, right? Is there any straightforward way to prove it?
$endgroup$
– Altun Hasanli
Jan 19 at 9:50
$begingroup$
@AltunHasanli: Well, it is an approximation, but there are theorems about how large the error in the approximation might be. Wikipedia has lots of results and references.
$endgroup$
– Nate Eldredge
Jan 19 at 15:37