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(fracn2))$Prove that $fracn^22 - 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?
What makes accurate emulation of old systems a difficult task?
Check if a string is entirely made of the same substring
Why must Chinese maps be obfuscated?
"The cow" OR "a cow" OR "cows" in this context
Overlay of two functions leaves gaps
How to have a sharp product image?
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?
Mistake in years of experience in resume?
Is Diceware more secure than a long passphrase?
What is the optimal strategy for the Dictionary Game?
Don’t seats that recline flat defeat the purpose of having seatbelts?
Could the terminal length of components like resistors be reduced?
Was there a shared-world project before "Thieves World"?
Like totally amazing interchangeable sister outfits II: The Revenge
I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?
Was there a Viking Exchange as well as a Columbian one?
Why does Mind Blank stop the Feeblemind spell?
Why boldmath fails in a tikz node?
Why didn't the Space Shuttle bounce back into space as many times as possible so as to lose a lot of kinetic energy up there?
Are there physical dangers to preparing a prepared piano?
How to limit Drive Letters Windows assigns to new removable USB drives
"You've called the wrong number" or "You called the wrong number"
How exactly does Hawking radiation decrease the mass of black holes?
Rivers without rain
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(fracn2))$Prove that $fracn^22 - 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 mathcalO(h(n)) $ and $ g(n) in mathcalO(h(n))$
Now it should hold: $$ fracf(n)g(n) =mathcalO(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, $$ fracf(n)g(n) = fracc_1c_2 cdot 1 forall ngeq maxN,N'$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
asked 10 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 mathcalO(h(n)) $ and $ g(n) in mathcalO(h(n))$
Now it should hold: $$ fracf(n)g(n) =mathcalO(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, $$ fracf(n)g(n) = fracc_1c_2 cdot 1 forall ngeq maxN,N'$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
asked 10 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
6 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 mathcalO(h(n)) $ and $ g(n) in mathcalO(h(n))$
Now it should hold: $$ fracf(n)g(n) =mathcalO(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, $$ fracf(n)g(n) = fracc_1c_2 cdot 1 forall ngeq maxN,N'$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
asked 10 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 mathcalO(h(n)) $ and $ g(n) in mathcalO(h(n))$
Now it should hold: $$ fracf(n)g(n) =mathcalO(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, $$ fracf(n)g(n) = fracc_1c_2 cdot 1 forall ngeq maxN,N'$$
I'm not sure. g(n) could be 0. What do you think?
real-analysis asymptotics
real-analysis asymptotics
asked 10 hours ago
Leon1998Leon1998
9010
asked 10 hours ago
Leon1998Leon1998
9010
asked 10 hours ago
Leon1998Leon1998
9010
asked 10 hours ago
Leon1998Leon1998
9010
asked 10 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
6 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
6 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
6 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
6 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 $fracfg = fracc_1c_2$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 10 hours ago
mihaildmihaild
1,974114
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 10 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 $fracfg = fracc_1c_2$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 10 hours ago
mihaildmihaild
1,974114
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
add a comment |
$begingroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $fracfg = fracc_1c_2$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 10 hours ago
mihaildmihaild
1,974114
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
add a comment |
$begingroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $fracfg = fracc_1c_2$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 10 hours ago
mihaildmihaild
1,974114
$endgroup$
You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $fracfg = fracc_1c_2$.
And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.
answered 10 hours ago
mihaildmihaild
1,974114
answered 10 hours ago
mihaildmihaild
1,974114
answered 10 hours ago
mihaildmihaild
1,974114
answered 10 hours ago
mihaildmihaild
1,974114
1,974114
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
add a comment |
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
$begingroup$
Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac13 neq frac24$. May be you wanted to write $fracfg leqslant fracc_1c_2$? It's still not true: you have $frac1g geqslant frac1c_2 h$, but you can multiply inequalities only with same direction.
$endgroup$
– mihaild
10 hours ago
1
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
10 hours ago
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 10 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 10 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 10 hours ago
FredFred
48.7k11849
$endgroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 10 hours ago
FredFred
48.7k11849
answered 10 hours ago
FredFred
48.7k11849
answered 10 hours ago
FredFred
48.7k11849
answered 10 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
6 hours ago