Understading the Big-oh notation
$begingroup$
My professor says that we use $f(x) = O(g(x))$ to mean that $g(x)$ is negligible compared to $f(x)$. Im kind of confused here. The definition I found online is
$$ f(x) = O(g(x)) iff exists C >0, ; ; st ; |f(x)| < C |g(x)| ; as ; x to 0$$
With this definition I can see that for example $x < e^x $ for $x to 0$ and so $x = O(e^x)$ how is $e^x$ negligible compared to $x$? Am I misunderstanding the concept completely?
calculus asymptotics
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
$endgroup$
add a comment |
$begingroup$
My professor says that we use $f(x) = O(g(x))$ to mean that $g(x)$ is negligible compared to $f(x)$. Im kind of confused here. The definition I found online is
$$ f(x) = O(g(x)) iff exists C >0, ; ; st ; |f(x)| < C |g(x)| ; as ; x to 0$$
With this definition I can see that for example $x < e^x $ for $x to 0$ and so $x = O(e^x)$ how is $e^x$ negligible compared to $x$? Am I misunderstanding the concept completely?
calculus asymptotics
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
$endgroup$
$begingroup$
Note that the definition of big-oh notation may have $x to infty$ or $x$ tending to some other limit, not necessarily zero. Regarding your question, I believe your professor misspoke; even if he/she used the more reasonable direction ("$f(x)$ is negligible compared to $g(x)$") it is not really something meant to be interpreted precisely, and is primarily to give you intuition. If you have any doubts, always go back to the definition.
$endgroup$
– angryavian
Jan 12 at 18:31
add a comment |
$begingroup$
My professor says that we use $f(x) = O(g(x))$ to mean that $g(x)$ is negligible compared to $f(x)$. Im kind of confused here. The definition I found online is
$$ f(x) = O(g(x)) iff exists C >0, ; ; st ; |f(x)| < C |g(x)| ; as ; x to 0$$
With this definition I can see that for example $x < e^x $ for $x to 0$ and so $x = O(e^x)$ how is $e^x$ negligible compared to $x$? Am I misunderstanding the concept completely?
calculus asymptotics
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
$endgroup$
My professor says that we use $f(x) = O(g(x))$ to mean that $g(x)$ is negligible compared to $f(x)$. Im kind of confused here. The definition I found online is
$$ f(x) = O(g(x)) iff exists C >0, ; ; st ; |f(x)| < C |g(x)| ; as ; x to 0$$
With this definition I can see that for example $x < e^x $ for $x to 0$ and so $x = O(e^x)$ how is $e^x$ negligible compared to $x$? Am I misunderstanding the concept completely?
calculus asymptotics
calculus asymptotics
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
asked Jan 12 at 18:26
Jimmy SabaterJimmy Sabater
2,662321
2,662321
$begingroup$
Note that the definition of big-oh notation may have $x to infty$ or $x$ tending to some other limit, not necessarily zero. Regarding your question, I believe your professor misspoke; even if he/she used the more reasonable direction ("$f(x)$ is negligible compared to $g(x)$") it is not really something meant to be interpreted precisely, and is primarily to give you intuition. If you have any doubts, always go back to the definition.
$endgroup$
– angryavian
Jan 12 at 18:31
add a comment |
$begingroup$
Note that the definition of big-oh notation may have $x to infty$ or $x$ tending to some other limit, not necessarily zero. Regarding your question, I believe your professor misspoke; even if he/she used the more reasonable direction ("$f(x)$ is negligible compared to $g(x)$") it is not really something meant to be interpreted precisely, and is primarily to give you intuition. If you have any doubts, always go back to the definition.
$endgroup$
– angryavian
Jan 12 at 18:31
$begingroup$
Note that the definition of big-oh notation may have $x to infty$ or $x$ tending to some other limit, not necessarily zero. Regarding your question, I believe your professor misspoke; even if he/she used the more reasonable direction ("$f(x)$ is negligible compared to $g(x)$") it is not really something meant to be interpreted precisely, and is primarily to give you intuition. If you have any doubts, always go back to the definition.
$endgroup$
– angryavian
Jan 12 at 18:31
$begingroup$
Note that the definition of big-oh notation may have $x to infty$ or $x$ tending to some other limit, not necessarily zero. Regarding your question, I believe your professor misspoke; even if he/she used the more reasonable direction ("$f(x)$ is negligible compared to $g(x)$") it is not really something meant to be interpreted precisely, and is primarily to give you intuition. If you have any doubts, always go back to the definition.
$endgroup$
– angryavian
Jan 12 at 18:31
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Personally, I would use the word "negligible" for Little-Oh. The way I like to think of it is
$$f(x)=O(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}<infty$$
and
$$f(x)=o(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}=0$$
So Big-Oh means "$f$ doesn't grow too much bigger than $g$" and Little-Oh means "$f$ becomes negligible compared to $g$"
answered Jan 12 at 18:53
pwerthpwerth
3,053417
$endgroup$
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
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%2f3071225%2funderstading-the-big-oh-notation%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$
Personally, I would use the word "negligible" for Little-Oh. The way I like to think of it is
$$f(x)=O(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}<infty$$
and
$$f(x)=o(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}=0$$
So Big-Oh means "$f$ doesn't grow too much bigger than $g$" and Little-Oh means "$f$ becomes negligible compared to $g$"
answered Jan 12 at 18:53
pwerthpwerth
3,053417
$endgroup$
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
add a comment |
$begingroup$
Personally, I would use the word "negligible" for Little-Oh. The way I like to think of it is
$$f(x)=O(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}<infty$$
and
$$f(x)=o(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}=0$$
So Big-Oh means "$f$ doesn't grow too much bigger than $g$" and Little-Oh means "$f$ becomes negligible compared to $g$"
answered Jan 12 at 18:53
pwerthpwerth
3,053417
$endgroup$
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
add a comment |
$begingroup$
Personally, I would use the word "negligible" for Little-Oh. The way I like to think of it is
$$f(x)=O(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}<infty$$
and
$$f(x)=o(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}=0$$
So Big-Oh means "$f$ doesn't grow too much bigger than $g$" and Little-Oh means "$f$ becomes negligible compared to $g$"
answered Jan 12 at 18:53
pwerthpwerth
3,053417
$endgroup$
Personally, I would use the word "negligible" for Little-Oh. The way I like to think of it is
$$f(x)=O(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}<infty$$
and
$$f(x)=o(g(x)) Leftrightarrow lim_{xtoinfty}frac{f(x)}{g(x)}=0$$
So Big-Oh means "$f$ doesn't grow too much bigger than $g$" and Little-Oh means "$f$ becomes negligible compared to $g$"
answered Jan 12 at 18:53
pwerthpwerth
3,053417
answered Jan 12 at 18:53
pwerthpwerth
3,053417
answered Jan 12 at 18:53
pwerthpwerth
3,053417
answered Jan 12 at 18:53
pwerthpwerth
3,053417
3,053417
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
add a comment |
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
So for example sin x doesnt grow too much bigger than x because sinx / x goes to 0 but sin x / x^2 goes to infinity so x^2 doesnt grow too much bigger than sin x right ?
$endgroup$
– Neymar
Jan 12 at 19:06
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar not quite. $sin{x}=o(x)$ and $sin{x}=o(x^{2})$ because both limits go to $0$. This is because $sin$ is always between $-1$ and $1$ but $x$ and $x^{2}$ (and in fact, any positive power of $x$) grow without bound as $xtoinfty$
$endgroup$
– pwerth
Jan 12 at 19:08
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
@Neymar I'll also mention that if $f(x)=o(g(x))$ then necessarily $f(x)=O(g(x))$, so the cases are not always disjoint. However we can certainly have $f(x)=O(g(x))$ without having $f(x)=o(g(x))$
$endgroup$
– pwerth
Jan 12 at 19:09
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
But sinx is big oh of x though
$endgroup$
– Neymar
Jan 12 at 19:12
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
$begingroup$
@Neymar Yes, it's also little oh of $x$. I suggest re-reading my other comments a bit more closely
$endgroup$
– pwerth
Jan 12 at 19:14
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%2f3071225%2funderstading-the-big-oh-notation%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$
Note that the definition of big-oh notation may have $x to infty$ or $x$ tending to some other limit, not necessarily zero. Regarding your question, I believe your professor misspoke; even if he/she used the more reasonable direction ("$f(x)$ is negligible compared to $g(x)$") it is not really something meant to be interpreted precisely, and is primarily to give you intuition. If you have any doubts, always go back to the definition.
$endgroup$
– angryavian
Jan 12 at 18:31