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?
The barbers paradox first order logic formalization
You look catfish vs You look like a catfish?
Pressure to defend the relevance of one's area of mathematics
I caught several of my students plagiarizing. Could it be my fault as a teacher?
CRT Oscilloscope - part of the plot is missing
Disabling Resource Governor in SQL Server
I’ve officially counted to infinity!
Power LED from 3.3V Power Pin without Resistor
Applying a function to a nested list
How to back up a running Linode server?
How do you center multiple equations that have multiple steps?
Why is the SNP putting so much emphasis on currency plans?
If Melisandre foresaw another character closing blue eyes, why did she follow Stannis?
What does air vanishing on contact sound like?
Is balancing necessary on a full-wheel change?
Field Length Validation for Desktop Application which has maximum 1000 characters
Why are notes ordered like they are on a piano?
Was Hulk present at this event?
Why is Thanos so tough at the beginning of "Avengers: Endgame"?
Survey Confirmation - Emphasize the question or the answer?
Unidentified items in bicycle tube repair kit
How did Arya manage to disguise herself?
Is it cheaper to drop cargo than to land it?
What happens if I start too many background jobs?
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 Apr 26 at 10:54
Leon1998Leon1998
10210
$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 Apr 26 at 10:54
Leon1998Leon1998
10210
$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
Apr 26 at 15:13
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 Apr 26 at 10:54
Leon1998Leon1998
10210
$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 Apr 26 at 10:54
Leon1998Leon1998
10210
asked Apr 26 at 10:54
Leon1998Leon1998
10210
asked Apr 26 at 10:54
Leon1998Leon1998
10210
asked Apr 26 at 10:54
Leon1998Leon1998
10210
asked Apr 26 at 10:54
Leon1998Leon1998
10210
10210
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
Apr 26 at 15:13
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
Apr 26 at 15:13
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
Apr 26 at 15:13
$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
Apr 26 at 15:13
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 Apr 26 at 11:00
mihaildmihaild
2,144216
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$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
Apr 26 at 11:06
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered Apr 26 at 11:02
FredFred
48.8k11849
$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 Apr 26 at 11:00
mihaildmihaild
2,144216
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$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
Apr 26 at 11:06
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
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 Apr 26 at 11:00
mihaildmihaild
2,144216
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$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
Apr 26 at 11:06
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
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 Apr 26 at 11:00
mihaildmihaild
2,144216
$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 Apr 26 at 11:00
mihaildmihaild
2,144216
answered Apr 26 at 11:00
mihaildmihaild
2,144216
answered Apr 26 at 11:00
mihaildmihaild
2,144216
answered Apr 26 at 11:00
mihaildmihaild
2,144216
2,144216
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$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
Apr 26 at 11:06
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
add a comment |
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$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
Apr 26 at 11:06
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
Apr 26 at 11:01
$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
Apr 26 at 11:06
$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
Apr 26 at 11:06
1
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
Apr 26 at 11:34
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered Apr 26 at 11:02
FredFred
48.8k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered Apr 26 at 11:02
FredFred
48.8k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered Apr 26 at 11:02
FredFred
48.8k11849
$endgroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered Apr 26 at 11:02
FredFred
48.8k11849
answered Apr 26 at 11:02
FredFred
48.8k11849
answered Apr 26 at 11:02
FredFred
48.8k11849
answered Apr 26 at 11:02
FredFred
48.8k11849
48.8k11849
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
Apr 26 at 15:13