Fdtxjr

Why does this part of the Space Shuttle launch pad seem to be floating in air?

Simulating a probability of 1 of 2^N with less than N random bits

Is a naturally all "male" species possible?

What to do when my ideas aren't chosen, when I strongly disagree with the chosen solution?

Would it be legal for a US State to ban exports of a natural resource?

Simple image editor tool to draw a simple box/rectangle in an existing image

How to check participants in at events?

Can the harmonic series explain the origin of the major scale?

Is there a good way to store credentials outside of a password manager?

word describing multiple paths to the same abstract outcome

Giant Toughroad SLR 2 for 200 miles in two days, will it make it?

Identify a stage play about a VR experience in which participants are encouraged to simulate performing horrific activities

Greatest common substring

How do ultrasonic sensors differentiate between transmitted and received signals?

node command while defining a coordinate in TikZ

How to prevent YouTube from showing already watched videos?

Could solar power be utilized and substitute coal in the 19th century?

How to deal with or prevent idle in the test team?

Is infinity mathematically observable?

Pronouncing Homer as in modern Greek

Reply ‘no position’ while the job posting is still there (‘HiWi’ position in Germany)

What will be the benefits of Brexit?

Are taller landing gear bad for aircraft, particulary large airliners?

Is it legal to discriminate due to the medicine used to treat a medical condition?

Big-$O$ verification [discrete mathematics]

Sets problem with upper boundsDiscrete Math - Logic - Implication ProblemLimit inferior and superior proof questionsDiscrete Mathematics - LogicExtend an acyclic relation to an orderingNon-homogenous linear recurrence relation reasonable TRIAL solution?Proof by Cases [discrete mathematics]Direct proof of Universal Set [discrete mathematics]Draw a pentagon with any 2 angle sums being less than $216^o$Indirect Proof [discrete mathematics]

-1

$begingroup$

I've come across challenge proof question in my discrete mathematics textbook that I'm trying to solve for practice but unfortunately it does not have a solution. Any help with a reasonable explanation or solution so that I can understand where to start and verify my work would be greatly appreciated:

Suppose that $f$, $g$ and $h$ are all functions from $mathbfN$ into
$mathbfR^+$. Prove that if $f + g notin O(h)$, then either $f
> notin O(h)$, or $g notin O(h)$ (or both).

Recall that $f in O(h)$ if and only if $exists c in mathbfR^+,
> exists n_0 in mathbfN, forall n in mathbfN, n ge n_0
> implies f(n) le ch(n)$. We define $f + g$ to be the function such
that $(f + g)(n) = f(n) + g(n)$ for every element $n$ of $mathbfN$.

Thank you!

discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics

share|cite|improve this question

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

$endgroup$

add a comment | 

-1

$begingroup$

I've come across challenge proof question in my discrete mathematics textbook that I'm trying to solve for practice but unfortunately it does not have a solution. Any help with a reasonable explanation or solution so that I can understand where to start and verify my work would be greatly appreciated:

Suppose that $f$, $g$ and $h$ are all functions from $mathbfN$ into
$mathbfR^+$. Prove that if $f + g notin O(h)$, then either $f
> notin O(h)$, or $g notin O(h)$ (or both).

Recall that $f in O(h)$ if and only if $exists c in mathbfR^+,
> exists n_0 in mathbfN, forall n in mathbfN, n ge n_0
> implies f(n) le ch(n)$. We define $f + g$ to be the function such
that $(f + g)(n) = f(n) + g(n)$ for every element $n$ of $mathbfN$.

Thank you!

discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics

share|cite|improve this question

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

$endgroup$

add a comment | 

$begingroup$

I've come across challenge proof question in my discrete mathematics textbook that I'm trying to solve for practice but unfortunately it does not have a solution. Any help with a reasonable explanation or solution so that I can understand where to start and verify my work would be greatly appreciated:

Suppose that $f$, $g$ and $h$ are all functions from $mathbfN$ into
$mathbfR^+$. Prove that if $f + g notin O(h)$, then either $f
> notin O(h)$, or $g notin O(h)$ (or both).

Recall that $f in O(h)$ if and only if $exists c in mathbfR^+,
> exists n_0 in mathbfN, forall n in mathbfN, n ge n_0
> implies f(n) le ch(n)$. We define $f + g$ to be the function such
that $(f + g)(n) = f(n) + g(n)$ for every element $n$ of $mathbfN$.

Thank you!

discrete-mathematics proof-verification proof-writing proof-explanation recreational-mathematics

share|cite|improve this question

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

$endgroup$

share|cite|improve this question

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

share|cite|improve this question

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

asked Mar 16 at 20:44

Joe BidenJoe Biden

25

1 Answer
1

active

oldest

votes

0

$begingroup$

$f+g notin O(h)$
means that,
for any $c > 0$,
there is a value of $x$
such that
$f(x)+g(x) > ch(x)$.

$f in O(h)$
means that,
for all large enough $x$,
there is a $c > 0$
such that
$f(x) < ch(x)$
and similarly for $g$.

If both
$f in O(h)$ and
$g in O(h)$
there are
$c_f$ and $c_g$
such that,
for all large enough $x$,
$f(x) < c_fh(x)$
and
$g(x) < c_gh(x)$.

Therefore,
for all large enough $x$,
$f(x)+g(x)
lt (c_f+c_g)h(x)$,
so that
$f+g in O(h)$.

share|cite|improve this answer

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3150825%2fbig-o-verification-discrete-mathematics%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

$f+g notin O(h)$
means that,
for any $c > 0$,
there is a value of $x$
such that
$f(x)+g(x) > ch(x)$.

$f in O(h)$
means that,
for all large enough $x$,
there is a $c > 0$
such that
$f(x) < ch(x)$
and similarly for $g$.

If both
$f in O(h)$ and
$g in O(h)$
there are
$c_f$ and $c_g$
such that,
for all large enough $x$,
$f(x) < c_fh(x)$
and
$g(x) < c_gh(x)$.

Therefore,
for all large enough $x$,
$f(x)+g(x)
lt (c_f+c_g)h(x)$,
so that
$f+g in O(h)$.

share|cite|improve this answer

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129

$endgroup$

add a comment | 

0

$begingroup$

$f+g notin O(h)$
means that,
for any $c > 0$,
there is a value of $x$
such that
$f(x)+g(x) > ch(x)$.

$f in O(h)$
means that,
for all large enough $x$,
there is a $c > 0$
such that
$f(x) < ch(x)$
and similarly for $g$.

If both
$f in O(h)$ and
$g in O(h)$
there are
$c_f$ and $c_g$
such that,
for all large enough $x$,
$f(x) < c_fh(x)$
and
$g(x) < c_gh(x)$.

Therefore,
for all large enough $x$,
$f(x)+g(x)
lt (c_f+c_g)h(x)$,
so that
$f+g in O(h)$.

share|cite|improve this answer

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129

$endgroup$

add a comment | 

$begingroup$

$f+g notin O(h)$
means that,
for any $c > 0$,
there is a value of $x$
such that
$f(x)+g(x) > ch(x)$.

$f in O(h)$
means that,
for all large enough $x$,
there is a $c > 0$
such that
$f(x) < ch(x)$
and similarly for $g$.

If both
$f in O(h)$ and
$g in O(h)$
there are
$c_f$ and $c_g$
such that,
for all large enough $x$,
$f(x) < c_fh(x)$
and
$g(x) < c_gh(x)$.

Therefore,
for all large enough $x$,
$f(x)+g(x)
lt (c_f+c_g)h(x)$,
so that
$f+g in O(h)$.

share|cite|improve this answer

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129

$endgroup$

share|cite|improve this answer

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129

answered Mar 16 at 21:13

marty cohenmarty cohen

74.6k549129