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?
How can I get rid of an unhelpful parallel branch when unpivoting a single row?
What does a straight horizontal line above a few notes, after a changed tempo mean?
Is the claim "Employers won't employ people with no 'social media presence'" realistic?
Why must Chinese maps be obfuscated?
Covering null sets by a finite number of intervals
How to pronounce 'c++' in Spanish
I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?
Who is the character that appears at the end of Endgame?
Could the terminal length of components like resistors be reduced?
Pulling the rope with one hand is as heavy as with two hands?
How could Tony Stark make this in Endgame?
Philosophical question on logistic regression: why isn't the optimal threshold value trained?
Could moose/elk survive in the Amazon forest?
How to read .npy file in Mathematica?
Big O /Right or wrong?
What does "function" actually mean in music?
How did Captain America use this in Avengers: Endgame?
Can't get 5V 3A DC constant
Is there a word for the censored part of a video?
Two field separators (colon and space) in awk
As an international instructor, should I openly talk about my accent?
Contradiction proof for inequality of P and NP?
diskutil list shows 20 disk partitions, I only know 3, what are the rest?
Can two odd numbers sum up to an odd number?
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 2 hours ago
Leon1998Leon1998
859
$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 2 hours ago
Leon1998Leon1998
859
$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 2 hours ago
Leon1998Leon1998
859
$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 2 hours ago
Leon1998Leon1998
859
asked 2 hours ago
Leon1998Leon1998
859
asked 2 hours ago
Leon1998Leon1998
859
asked 2 hours ago
Leon1998Leon1998
859
asked 2 hours ago
Leon1998Leon1998
859
859
add a comment |
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 2 hours ago
mihaildmihaild
1,82913
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 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
2 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 hours ago
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 2 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 2 hours ago
mihaildmihaild
1,82913
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 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
2 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 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 2 hours ago
mihaildmihaild
1,82913
$endgroup$
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 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
2 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 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 2 hours ago
mihaildmihaild
1,82913
$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 2 hours ago
mihaildmihaild
1,82913
answered 2 hours ago
mihaildmihaild
1,82913
answered 2 hours ago
mihaildmihaild
1,82913
answered 2 hours ago
mihaildmihaild
1,82913
1,82913
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 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
2 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 hours ago
add a comment |
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 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
2 hours ago
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 hours ago
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 hours ago
$begingroup$
Why can't I go to $ fracfg$
$endgroup$
– Leon1998
2 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
2 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
2 hours ago
1
1
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 hours ago
$begingroup$
Ok thank you. Now I see my mistake:)
$endgroup$
– Leon1998
2 hours ago
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 2 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 2 hours ago
FredFred
48.7k11849
$endgroup$
add a comment |
$begingroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 2 hours ago
FredFred
48.7k11849
$endgroup$
Consider $f(n)=h(n)=1$ and $g(n)=1/n$.
answered 2 hours ago
FredFred
48.7k11849
answered 2 hours ago
FredFred
48.7k11849
answered 2 hours ago
FredFred
48.7k11849
answered 2 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
