Result of multiplying both sides of not-big-O relationship by the same function?List of Big-O for PHP functionsI need help proving that if f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n)))Determining complexity for recursive functions (Big O notation)comparing 2 functions with big O notationBig-O and Function DominationWhat makes two functions have fundamentally different efficiency times in Big O notationBig O as an exponent on both sides?multiplying 2 functions that are both big O of a thirdThe Mathematical Relationship Between Big-Oh ClassesBig Theta of Factorial Multiplied by a Coefficient
Efficient Algorithm for the boundary of a set of tiles
How can I tell if I'm being too picky as a referee?
Defining the standard model of PA so that a space alien could understand
Why most published works in medical imaging try reducing false positives?
Ingress filtering on edge routers and performance concerns
I know that there is a preselected candidate for a position to be filled at my department. What should I do?
How to attach cable mounting points to a bicycle frame?
What was the idiom for something that we take without a doubt?
Website returning plaintext password
Do photons bend spacetime or not?
Best material to absorb as much light as possible
Count rotary dial pulses in a phone number (including letters)
Sankey diagram: not getting the hang of it
Need to understand my home electrical meter to see why bill is so high and/or if neighbor is on same meter
How to cut a climbing rope?
The art of clickbait captions
USPS Back Room - Trespassing?
Value of a binomial series
Does pair production happen even when the photon is around a neutron?
What is the function of the corrugations on a section of the Space Shuttle's external tank?
Is Jon Snow the last of his House?
Why did Theresa May offer a vote on a second Brexit referendum?
Where have Brexit voters gone?
Why aren't space telescopes put in GEO?
Result of multiplying both sides of not-big-O relationship by the same function?
List of Big-O for PHP functionsI need help proving that if f(n) = O(g(n)) implies 2^(f(n)) = O(2^g(n)))Determining complexity for recursive functions (Big O notation)comparing 2 functions with big O notationBig-O and Function DominationWhat makes two functions have fundamentally different efficiency times in Big O notationBig O as an exponent on both sides?multiplying 2 functions that are both big O of a thirdThe Mathematical Relationship Between Big-Oh ClassesBig Theta of Factorial Multiplied by a Coefficient
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
Is the following generally true?f∉O(g) ⇒ f*h∉O(g*h)
Where f, h, g are positive-only functions. My intuition is that it is true, but I don't know how to prove it.
Here is why I think it is true:
Because f∉O(g) there is no c multiplied by g that will make f ≤ c*g for a large enough x. There is no valid c for g because either f and g alternate who is on top or f dominates g. For each x, the point f(x) and g(x) will be scaled by h(x), therefore if f(x) is above g(x), then h(x)f(x) will be above h(x)g(x). This would mean the lack of asymptotic dominance must remain the same when multiplied by h, right?
big-o complexity-theory
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
add a comment |
Is the following generally true?f∉O(g) ⇒ f*h∉O(g*h)
Where f, h, g are positive-only functions. My intuition is that it is true, but I don't know how to prove it.
Here is why I think it is true:
Because f∉O(g) there is no c multiplied by g that will make f ≤ c*g for a large enough x. There is no valid c for g because either f and g alternate who is on top or f dominates g. For each x, the point f(x) and g(x) will be scaled by h(x), therefore if f(x) is above g(x), then h(x)f(x) will be above h(x)g(x). This would mean the lack of asymptotic dominance must remain the same when multiplied by h, right?
big-o complexity-theory
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
not true if for instance h is always a fraction i.e. 0 ≤ h ≤ 1. in that case g * h ≤ g which means that we may find a constant c for g * h
– mangusta
Mar 24 at 2:57
add a comment |
Is the following generally true?f∉O(g) ⇒ f*h∉O(g*h)
Where f, h, g are positive-only functions. My intuition is that it is true, but I don't know how to prove it.
Here is why I think it is true:
Because f∉O(g) there is no c multiplied by g that will make f ≤ c*g for a large enough x. There is no valid c for g because either f and g alternate who is on top or f dominates g. For each x, the point f(x) and g(x) will be scaled by h(x), therefore if f(x) is above g(x), then h(x)f(x) will be above h(x)g(x). This would mean the lack of asymptotic dominance must remain the same when multiplied by h, right?
big-o complexity-theory
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
Is the following generally true?f∉O(g) ⇒ f*h∉O(g*h)
Where f, h, g are positive-only functions. My intuition is that it is true, but I don't know how to prove it.
Here is why I think it is true:
Because f∉O(g) there is no c multiplied by g that will make f ≤ c*g for a large enough x. There is no valid c for g because either f and g alternate who is on top or f dominates g. For each x, the point f(x) and g(x) will be scaled by h(x), therefore if f(x) is above g(x), then h(x)f(x) will be above h(x)g(x). This would mean the lack of asymptotic dominance must remain the same when multiplied by h, right?
big-o complexity-theory
big-o complexity-theory
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
edited Mar 24 at 2:42
Austin Gibb
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
asked Mar 24 at 2:37
Austin GibbAustin Gibb
103211
103211
not true if for instance h is always a fraction i.e. 0 ≤ h ≤ 1. in that case g * h ≤ g which means that we may find a constant c for g * h
– mangusta
Mar 24 at 2:57
add a comment |
not true if for instance h is always a fraction i.e. 0 ≤ h ≤ 1. in that case g * h ≤ g which means that we may find a constant c for g * h
– mangusta
Mar 24 at 2:57
not true if for instance h is always a fraction i.e. 0 ≤ h ≤ 1. in that case g * h ≤ g which means that we may find a constant c for g * h
– mangusta
Mar 24 at 2:57
not true if for instance h is always a fraction i.e. 0 ≤ h ≤ 1. in that case g * h ≤ g which means that we may find a constant c for g * h
– mangusta
Mar 24 at 2:57
add a comment |
1 Answer
1
active
oldest
votes
Suppose f * h is O(g * h). Then there exist x0, c such that f(x) * h(x) <= c * g(x) * h(x) for all x >= x0. Since h is always positive, h(x) is positive and we are free to divide both sides of the inequality without changing sign. This yields f(x) <= c * g(x). Therefore, f * h in O(g * h) implies f in O(g).
What we have just shown to be true is the contrapositive of your claim. Your claim to prove is:
if f is not O(g), then f * h is not O(g * h)
What we have just shown is:
if f * h is O(g * h), then f is O(g)
Because all logical statements are logically equivalent to their contrapositives, your statement is also true. You can reason directly by multiplying one side of the inequality by the unity h(x)/h(x) and then multiplying through by h(x); but I thought canceling by division was clearer.
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
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%2fstackoverflow.com%2fquestions%2f55320278%2fresult-of-multiplying-both-sides-of-not-big-o-relationship-by-the-same-function%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
Suppose f * h is O(g * h). Then there exist x0, c such that f(x) * h(x) <= c * g(x) * h(x) for all x >= x0. Since h is always positive, h(x) is positive and we are free to divide both sides of the inequality without changing sign. This yields f(x) <= c * g(x). Therefore, f * h in O(g * h) implies f in O(g).
What we have just shown to be true is the contrapositive of your claim. Your claim to prove is:
if f is not O(g), then f * h is not O(g * h)
What we have just shown is:
if f * h is O(g * h), then f is O(g)
Because all logical statements are logically equivalent to their contrapositives, your statement is also true. You can reason directly by multiplying one side of the inequality by the unity h(x)/h(x) and then multiplying through by h(x); but I thought canceling by division was clearer.
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
add a comment |
Suppose f * h is O(g * h). Then there exist x0, c such that f(x) * h(x) <= c * g(x) * h(x) for all x >= x0. Since h is always positive, h(x) is positive and we are free to divide both sides of the inequality without changing sign. This yields f(x) <= c * g(x). Therefore, f * h in O(g * h) implies f in O(g).
What we have just shown to be true is the contrapositive of your claim. Your claim to prove is:
if f is not O(g), then f * h is not O(g * h)
What we have just shown is:
if f * h is O(g * h), then f is O(g)
Because all logical statements are logically equivalent to their contrapositives, your statement is also true. You can reason directly by multiplying one side of the inequality by the unity h(x)/h(x) and then multiplying through by h(x); but I thought canceling by division was clearer.
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
add a comment |
Suppose f * h is O(g * h). Then there exist x0, c such that f(x) * h(x) <= c * g(x) * h(x) for all x >= x0. Since h is always positive, h(x) is positive and we are free to divide both sides of the inequality without changing sign. This yields f(x) <= c * g(x). Therefore, f * h in O(g * h) implies f in O(g).
What we have just shown to be true is the contrapositive of your claim. Your claim to prove is:
if f is not O(g), then f * h is not O(g * h)
What we have just shown is:
if f * h is O(g * h), then f is O(g)
Because all logical statements are logically equivalent to their contrapositives, your statement is also true. You can reason directly by multiplying one side of the inequality by the unity h(x)/h(x) and then multiplying through by h(x); but I thought canceling by division was clearer.
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
Suppose f * h is O(g * h). Then there exist x0, c such that f(x) * h(x) <= c * g(x) * h(x) for all x >= x0. Since h is always positive, h(x) is positive and we are free to divide both sides of the inequality without changing sign. This yields f(x) <= c * g(x). Therefore, f * h in O(g * h) implies f in O(g).
What we have just shown to be true is the contrapositive of your claim. Your claim to prove is:
if f is not O(g), then f * h is not O(g * h)
What we have just shown is:
if f * h is O(g * h), then f is O(g)
Because all logical statements are logically equivalent to their contrapositives, your statement is also true. You can reason directly by multiplying one side of the inequality by the unity h(x)/h(x) and then multiplying through by h(x); but I thought canceling by division was clearer.
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
edited Mar 26 at 2:44
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
answered Mar 25 at 15:02
Patrick87Patrick87
19k32760
19k32760
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
add a comment |
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
In the first paragraph, "This yields f(x) <= c * g(x) * h(x)." should read "This yields f(x) <= c * g(x)."
– Leandro Caniglia
Mar 25 at 20:12
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
@LeandroCaniglia you're right, thanks
– Patrick87
Mar 26 at 2:44
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f55320278%2fresult-of-multiplying-both-sides-of-not-big-o-relationship-by-the-same-function%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
not true if for instance h is always a fraction i.e. 0 ≤ h ≤ 1. in that case g * h ≤ g which means that we may find a constant c for g * h
– mangusta
Mar 24 at 2:57