Mixing
How to prove the Big-Oh for the following statements?
$begingroup$
I have learned to prove Big-Oh for statements containing only polynomial functions. But I am having a hard time solving the following ones because they happen to have many types of function in one statement, like logarithmic and polynomial and exponential in the same statement. I have approached in the way which I use to proof for polynomial times, but with this statements, appraoching in that style is not giving any result. Here are the problems
Sorry for poor formatting of the equations.
- $1000n^2 + 16n + 2^n$
- $nlog(n) + 15n + 0.002n^2$
- $37n + nlog(n^2) + 5000log(n)$
I know the answer of them to be $O(2^n)$, $O(n^2)$, $O(nlog(n^2))$. But I think I have not been able to prove them in a formal way.
What I have done so far is, As I have to prove $f(n) leq cg(n)$, for $n geq k$, I take some arbitrary values of $k$, like set $k$ to $1$, and try to find the value of $c$ from the equation. What I want to know, how to formally prove this?
functions asymptotics
edited Jan 22 at 9:36
Henrik
6,03592030
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
$endgroup$
add a comment |
$begingroup$
I have learned to prove Big-Oh for statements containing only polynomial functions. But I am having a hard time solving the following ones because they happen to have many types of function in one statement, like logarithmic and polynomial and exponential in the same statement. I have approached in the way which I use to proof for polynomial times, but with this statements, appraoching in that style is not giving any result. Here are the problems
Sorry for poor formatting of the equations.
- $1000n^2 + 16n + 2^n$
- $nlog(n) + 15n + 0.002n^2$
- $37n + nlog(n^2) + 5000log(n)$
I know the answer of them to be $O(2^n)$, $O(n^2)$, $O(nlog(n^2))$. But I think I have not been able to prove them in a formal way.
What I have done so far is, As I have to prove $f(n) leq cg(n)$, for $n geq k$, I take some arbitrary values of $k$, like set $k$ to $1$, and try to find the value of $c$ from the equation. What I want to know, how to formally prove this?
functions asymptotics
edited Jan 22 at 9:36
Henrik
6,03592030
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
$endgroup$
$begingroup$
You can evaluate the limits of the given expressions over the big-O functions and check that they are finite.
$endgroup$
– Yves Daoust
Jan 2 '18 at 15:09
$begingroup$
Can you describe more? Or show an example?
$endgroup$
– Redwanul Sourav
Jan 2 '18 at 15:11
add a comment |
$begingroup$
I have learned to prove Big-Oh for statements containing only polynomial functions. But I am having a hard time solving the following ones because they happen to have many types of function in one statement, like logarithmic and polynomial and exponential in the same statement. I have approached in the way which I use to proof for polynomial times, but with this statements, appraoching in that style is not giving any result. Here are the problems
Sorry for poor formatting of the equations.
- $1000n^2 + 16n + 2^n$
- $nlog(n) + 15n + 0.002n^2$
- $37n + nlog(n^2) + 5000log(n)$
I know the answer of them to be $O(2^n)$, $O(n^2)$, $O(nlog(n^2))$. But I think I have not been able to prove them in a formal way.
What I have done so far is, As I have to prove $f(n) leq cg(n)$, for $n geq k$, I take some arbitrary values of $k$, like set $k$ to $1$, and try to find the value of $c$ from the equation. What I want to know, how to formally prove this?
functions asymptotics
edited Jan 22 at 9:36
Henrik
6,03592030
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
$endgroup$
I have learned to prove Big-Oh for statements containing only polynomial functions. But I am having a hard time solving the following ones because they happen to have many types of function in one statement, like logarithmic and polynomial and exponential in the same statement. I have approached in the way which I use to proof for polynomial times, but with this statements, appraoching in that style is not giving any result. Here are the problems
Sorry for poor formatting of the equations.
- $1000n^2 + 16n + 2^n$
- $nlog(n) + 15n + 0.002n^2$
- $37n + nlog(n^2) + 5000log(n)$
I know the answer of them to be $O(2^n)$, $O(n^2)$, $O(nlog(n^2))$. But I think I have not been able to prove them in a formal way.
What I have done so far is, As I have to prove $f(n) leq cg(n)$, for $n geq k$, I take some arbitrary values of $k$, like set $k$ to $1$, and try to find the value of $c$ from the equation. What I want to know, how to formally prove this?
functions asymptotics
functions asymptotics
edited Jan 22 at 9:36
Henrik
6,03592030
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
edited Jan 22 at 9:36
Henrik
6,03592030
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
edited Jan 22 at 9:36
Henrik
6,03592030
edited Jan 22 at 9:36
Henrik
6,03592030
edited Jan 22 at 9:36
Henrik
6,03592030
6,03592030
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
asked Jan 2 '18 at 15:04
Redwanul SouravRedwanul Sourav
10626
10626
$begingroup$
You can evaluate the limits of the given expressions over the big-O functions and check that they are finite.
$endgroup$
– Yves Daoust
Jan 2 '18 at 15:09
$begingroup$
Can you describe more? Or show an example?
$endgroup$
– Redwanul Sourav
Jan 2 '18 at 15:11
add a comment |
$begingroup$
You can evaluate the limits of the given expressions over the big-O functions and check that they are finite.
$endgroup$
– Yves Daoust
Jan 2 '18 at 15:09
$begingroup$
Can you describe more? Or show an example?
$endgroup$
– Redwanul Sourav
Jan 2 '18 at 15:11
$begingroup$
You can evaluate the limits of the given expressions over the big-O functions and check that they are finite.
$endgroup$
– Yves Daoust
Jan 2 '18 at 15:09
$begingroup$
You can evaluate the limits of the given expressions over the big-O functions and check that they are finite.
$endgroup$
– Yves Daoust
Jan 2 '18 at 15:09
$begingroup$
Can you describe more? Or show an example?
$endgroup$
– Redwanul Sourav
Jan 2 '18 at 15:11
$begingroup$
Can you describe more? Or show an example?
$endgroup$
– Redwanul Sourav
Jan 2 '18 at 15:11
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
You have to use a scale of comparison, which here will be made up of functions of type:
$$log^alpha! n :n^beta, 2^{gamma n}.$$
Now these functions are totally ordered, by the relation $f=o(g)$, that we'll denote $: fprec g$.
This order is identical to the lexicographic order on the triplets $(alpha,beta, gamma)$, so that
$$log nprec nprec nlog n prec n^2 prec 2^n$$
and
$f(n)=1000n^2 + 16n + 2^n=2^n+obigl(2^nbigr)sim_infty 2^n$, so $color{red}{f(n)=Obigl(2^nbigr)}$.
$g(n)=nlog(n) + 15n + 0.002n^2= 0.002n^2+o(n^2)sim_infty 0.002n^2 $, so $color{red}{g(n)=O(n^2)}$.
$h(n)=37n + nlog(n^2) + 5000log(n)=2nlog n+o(nlog n)sim_infty 2nlog n$, so $color{red}{h(n)=O(nlog n)}$.
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
$endgroup$
add a 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%2f2588899%2fhow-to-prove-the-big-oh-for-the-following-statements%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$
You have to use a scale of comparison, which here will be made up of functions of type:
$$log^alpha! n :n^beta, 2^{gamma n}.$$
Now these functions are totally ordered, by the relation $f=o(g)$, that we'll denote $: fprec g$.
This order is identical to the lexicographic order on the triplets $(alpha,beta, gamma)$, so that
$$log nprec nprec nlog n prec n^2 prec 2^n$$
and
$f(n)=1000n^2 + 16n + 2^n=2^n+obigl(2^nbigr)sim_infty 2^n$, so $color{red}{f(n)=Obigl(2^nbigr)}$.
$g(n)=nlog(n) + 15n + 0.002n^2= 0.002n^2+o(n^2)sim_infty 0.002n^2 $, so $color{red}{g(n)=O(n^2)}$.
$h(n)=37n + nlog(n^2) + 5000log(n)=2nlog n+o(nlog n)sim_infty 2nlog n$, so $color{red}{h(n)=O(nlog n)}$.
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
$endgroup$
add a comment |
$begingroup$
You have to use a scale of comparison, which here will be made up of functions of type:
$$log^alpha! n :n^beta, 2^{gamma n}.$$
Now these functions are totally ordered, by the relation $f=o(g)$, that we'll denote $: fprec g$.
This order is identical to the lexicographic order on the triplets $(alpha,beta, gamma)$, so that
$$log nprec nprec nlog n prec n^2 prec 2^n$$
and
$f(n)=1000n^2 + 16n + 2^n=2^n+obigl(2^nbigr)sim_infty 2^n$, so $color{red}{f(n)=Obigl(2^nbigr)}$.
$g(n)=nlog(n) + 15n + 0.002n^2= 0.002n^2+o(n^2)sim_infty 0.002n^2 $, so $color{red}{g(n)=O(n^2)}$.
$h(n)=37n + nlog(n^2) + 5000log(n)=2nlog n+o(nlog n)sim_infty 2nlog n$, so $color{red}{h(n)=O(nlog n)}$.
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
$endgroup$
add a comment |
$begingroup$
You have to use a scale of comparison, which here will be made up of functions of type:
$$log^alpha! n :n^beta, 2^{gamma n}.$$
Now these functions are totally ordered, by the relation $f=o(g)$, that we'll denote $: fprec g$.
This order is identical to the lexicographic order on the triplets $(alpha,beta, gamma)$, so that
$$log nprec nprec nlog n prec n^2 prec 2^n$$
and
$f(n)=1000n^2 + 16n + 2^n=2^n+obigl(2^nbigr)sim_infty 2^n$, so $color{red}{f(n)=Obigl(2^nbigr)}$.
$g(n)=nlog(n) + 15n + 0.002n^2= 0.002n^2+o(n^2)sim_infty 0.002n^2 $, so $color{red}{g(n)=O(n^2)}$.
$h(n)=37n + nlog(n^2) + 5000log(n)=2nlog n+o(nlog n)sim_infty 2nlog n$, so $color{red}{h(n)=O(nlog n)}$.
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
$endgroup$
You have to use a scale of comparison, which here will be made up of functions of type:
$$log^alpha! n :n^beta, 2^{gamma n}.$$
Now these functions are totally ordered, by the relation $f=o(g)$, that we'll denote $: fprec g$.
This order is identical to the lexicographic order on the triplets $(alpha,beta, gamma)$, so that
$$log nprec nprec nlog n prec n^2 prec 2^n$$
and
$f(n)=1000n^2 + 16n + 2^n=2^n+obigl(2^nbigr)sim_infty 2^n$, so $color{red}{f(n)=Obigl(2^nbigr)}$.
$g(n)=nlog(n) + 15n + 0.002n^2= 0.002n^2+o(n^2)sim_infty 0.002n^2 $, so $color{red}{g(n)=O(n^2)}$.
$h(n)=37n + nlog(n^2) + 5000log(n)=2nlog n+o(nlog n)sim_infty 2nlog n$, so $color{red}{h(n)=O(nlog n)}$.
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
answered Jan 2 '18 at 15:27
BernardBernard
122k741116
122k741116
add a comment |
add a 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%2f2588899%2fhow-to-prove-the-big-oh-for-the-following-statements%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$
You can evaluate the limits of the given expressions over the big-O functions and check that they are finite.
$endgroup$
– Yves Daoust
Jan 2 '18 at 15:09
$begingroup$
Can you describe more? Or show an example?
$endgroup$
– Redwanul Sourav
Jan 2 '18 at 15:11