Big O /Right or wrong?Prove $O(x)+O(x^2)=O(x^2)$ (Big O Notation)$f(n) in o(g(n))$ and $g(n) in o(f(n))$Prove...
Rivers without rain
Do I have an "anti-research" personality?
A strange hotel
What makes accurate emulation of old systems a difficult task?
I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?
Why was the Spitfire's elliptical wing almost uncopied by other aircraft of World War 2?
How do I deal with a coworker that keeps asking to make small superficial changes to a report, and it is seriously triggering my anxiety?
Phrase for the opposite of "foolproof"
Critique of timeline aesthetic
Alignment of various blocks in tikz
Is there really no use for MD5 anymore?
How to write a column outside the braces in a matrix?
Does tea made with boiling water cool faster than tea made with boiled (but still hot) water?
What's the name of these pliers?
Why must Chinese maps be obfuscated?
What are the steps to solving this definite integral?
"Whatever a Russian does, they end up making the Kalashnikov gun"? Are there any similar proverbs in English?
A Note on N!
acheter à, to mean both "from" and "for"?
How to limit Drive Letters Windows assigns to new removable USB drives
How to display Aura JS Errors Lightning Out
Dynamic SOQL query relationship with field visibility for Users
Elements other than carbon that can form many different compounds by bonding to themselves?
How exactly does Hawking radiation decrease the mass of black holes?
Big O /Right or wrong?
Prove $O(x)+O(x^2)=O(x^2)$ (Big O Notation)$f(n) in o(g(n))$ and $g(n) in o(f(n))$Prove or disapprove the statement: $f(n)=Theta(f(frac{n}{2}))$Prove that $frac{n^2}{2} - 3n = Theta(n^2)$Algorithm Theta Notation : How constant $c_2 geq 1/2$ is derived from the inequality $c_1 leq 1/2 - 3/n leq c_2$How to prove Big Theta on polynomial function?Prove $O(n+log(n)) subset O(n cdot log(n))$How to prove big theta inequality?Asymptotic notations - Big Omega ProofStrange big-O notation?
$begingroup$
I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:
$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$
Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(1) $$
By definition I get: $f(n) leq c_1 cdot h(n) forall ngeq N$ and $g(n) leq c_2 cdot h(n) forall ngeq N'$
So, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
asked 17 hours ago
Leon1998Leon1998
9010
$endgroup$
add a comment |
$begingroup$
I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:
$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$
Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(1) $$
By definition I get: $f(n) leq c_1 cdot h(n) forall ngeq N$ and $g(n) leq c_2 cdot h(n) forall ngeq N'$
So, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
asked 17 hours ago
Leon1998Leon1998
9010
$endgroup$
3
$begingroup$
I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly?
$endgroup$
– Eric Lippert
13 hours ago
add a comment |
$begingroup$
I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:
$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$
Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(1) $$
By definition I get: $f(n) leq c_1 cdot h(n) forall ngeq N$ and $g(n) leq c_2 cdot h(n) forall ngeq N'$
So, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
asked 17 hours ago
Leon1998Leon1998
9010
$endgroup$
I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:
$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$
Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(1) $$
By definition I get: $f(n) leq c_1 cdot h(n) forall ngeq N$ and $g(n) leq c_2 cdot h(n) forall ngeq N'$
So, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
real-analysis asymptotics
asked 17 hours ago
Leon1998Leon1998
9010
asked 17 hours ago
Leon1998Leon1998
9010
asked 17 hours ago
Leon1998Leon1998
9010
asked 17 hours ago
Leon1998Leon1998
9010
asked 17 hours ago
Leon1998Leon1998
9010
9010
3
$begingroup$
I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly?
$endgroup$
– Eric Lippert
13 hours ago
add a comment |
3
$begingroup$
I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly?
$endgroup$
– Eric Lippert
13 hours ago
3
3
$begingroup$
I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly?
$endgroup$
– Eric Lippert
13 hours ago
$begingroup$
I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly?
$endgroup$
– Eric Lippert
13 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 17 hours ago
mihaildmihaild
1,974114
$endgroup$
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 17 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
Your Answer
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%2f3203115%2fbig-o-right-or-wrong%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 17 hours ago
mihaildmihaild
1,974114
$endgroup$
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
add a comment |
$begingroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 17 hours ago
mihaildmihaild
1,974114
$endgroup$
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
add a comment |
$begingroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 17 hours ago
mihaildmihaild
1,974114
$endgroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 17 hours ago
mihaildmihaild
1,974114
answered 17 hours ago
mihaildmihaild
1,974114
answered 17 hours ago
mihaildmihaild
1,974114
answered 17 hours ago
mihaildmihaild
1,974114
1,974114
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
add a comment |
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Why can't I go to $ frac{f}{g}$
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
17 hours ago
1
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
17 hours ago
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 17 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 17 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 17 hours ago
FredFred
48.7k11849
$endgroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 17 hours ago
FredFred
48.7k11849
answered 17 hours ago
FredFred
48.7k11849
answered 17 hours ago
FredFred
48.7k11849
answered 17 hours ago
FredFred
48.7k11849
48.7k11849
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%2f3203115%2fbig-o-right-or-wrong%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
3
$begingroup$
I don't understand why you went from saying f and g are elements of O(something) to f/g being equal to O(1). O(1) is a set, and f/g is a function, so surely the question is whether it is an element of O(1), right? Was this a typo? Can you explain the question more clearly?
$endgroup$
– Eric Lippert
13 hours ago