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...

Rivers without rain

Do I have an "anti-research" personality?

A strange hotel

What makes accurate emulation of old systems a difficult task?

I preordered a game on my Xbox while on the home screen of my friend's account. Which of us owns the game?

Why was the Spitfire's elliptical wing almost uncopied by other aircraft of World War 2?

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?

Phrase for the opposite of "foolproof"

Critique of timeline aesthetic

Alignment of various blocks in tikz

Is there really no use for MD5 anymore?

How to write a column outside the braces in a matrix?

Does tea made with boiling water cool faster than tea made with boiled (but still hot) water?

What's the name of these pliers?

Why must Chinese maps be obfuscated?

What are the steps to solving this definite integral?

"Whatever a Russian does, they end up making the Kalashnikov gun"? Are there any similar proverbs in English?

A ​Note ​on ​N!

acheter à, to mean both "from" and "for"?

How to limit Drive Letters Windows assigns to new removable USB drives

How to display Aura JS Errors Lightning Out

Dynamic SOQL query relationship with field visibility for Users

Elements other than carbon that can form many different compounds by bonding to themselves?

How exactly does Hawking radiation decrease the mass of black holes?



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(frac{n}{2}))$Prove that $frac{n^2}{2} - 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?













4












$begingroup$


I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:



$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$



Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(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, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$



I'm not sure. g(n) could be 0. What do you think?






real-analysis asymptotics







share|cite|improve this question









$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
    13 hours ago


















4












$begingroup$


I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:



$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$



Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(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, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$



I'm not sure. g(n) could be 0. What do you think?






real-analysis asymptotics







share|cite|improve this question









$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
    13 hours ago
















4












4








4


1



$begingroup$


I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:



$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$



Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(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, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$



I'm not sure. g(n) could be 0. What do you think?






real-analysis asymptotics







share|cite|improve this question









$endgroup$




I have to decide, wether the following theorem is right or wrong.
There are functions, that satisfy the following conditions:



$ f(n) in mathcal{O}(h(n)) $ and $ g(n) in mathcal{O}(h(n))$



Now it should hold: $$ frac{f(n)}{g(n)} =mathcal{O}(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, $$ frac{f(n)}{g(n)} = frac{c_1}{c_2} cdot 1 forall ngeq max{N,N'}$$



I'm not sure. g(n) could be 0. What do you think?






real-analysis asymptotics




real-analysis asymptotics






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 17 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
    13 hours ago
















  • 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
    13 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
13 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
13 hours ago












2 Answers
2






active

oldest

votes


















12












$begingroup$

You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.



And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Why can't I go to $ frac{f}{g}$
    $endgroup$
    – Leon1998
    17 hours ago












  • $begingroup$
    Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
    $endgroup$
    – mihaild
    17 hours ago








  • 1




    $begingroup$
    Ok thank you. Now I see my mistake:)
    $endgroup$
    – Leon1998
    17 hours ago



















7












$begingroup$

Consider $f(n)=h(n)=1$ and $g(n)=1/n$.






share|cite|improve this answer









$endgroup$














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


    }
    });














    draft saved

    draft discarded


















    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









    12












    $begingroup$

    You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.



    And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Why can't I go to $ frac{f}{g}$
      $endgroup$
      – Leon1998
      17 hours ago












    • $begingroup$
      Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
      $endgroup$
      – mihaild
      17 hours ago








    • 1




      $begingroup$
      Ok thank you. Now I see my mistake:)
      $endgroup$
      – Leon1998
      17 hours ago
















    12












    $begingroup$

    You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.



    And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Why can't I go to $ frac{f}{g}$
      $endgroup$
      – Leon1998
      17 hours ago












    • $begingroup$
      Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
      $endgroup$
      – mihaild
      17 hours ago








    • 1




      $begingroup$
      Ok thank you. Now I see my mistake:)
      $endgroup$
      – Leon1998
      17 hours ago














    12












    12








    12





    $begingroup$

    You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.



    And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.






    share|cite|improve this answer









    $endgroup$



    You can't go from $f leqslant c_1 h$ and $g leqslant c_2 h$ to $frac{f}{g} = frac{c_1}{c_2}$.



    And the initial claim is false. Take, for example, $f(n) = h(n) = n^2$, $g(n) = n$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 17 hours ago









    mihaildmihaild

    1,974114




    1,974114












    • $begingroup$
      Why can't I go to $ frac{f}{g}$
      $endgroup$
      – Leon1998
      17 hours ago












    • $begingroup$
      Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
      $endgroup$
      – mihaild
      17 hours ago








    • 1




      $begingroup$
      Ok thank you. Now I see my mistake:)
      $endgroup$
      – Leon1998
      17 hours ago


















    • $begingroup$
      Why can't I go to $ frac{f}{g}$
      $endgroup$
      – Leon1998
      17 hours ago












    • $begingroup$
      Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
      $endgroup$
      – mihaild
      17 hours ago








    • 1




      $begingroup$
      Ok thank you. Now I see my mistake:)
      $endgroup$
      – Leon1998
      17 hours ago
















    $begingroup$
    Why can't I go to $ frac{f}{g}$
    $endgroup$
    – Leon1998
    17 hours ago






    $begingroup$
    Why can't I go to $ frac{f}{g}$
    $endgroup$
    – Leon1998
    17 hours ago














    $begingroup$
    Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
    $endgroup$
    – mihaild
    17 hours ago






    $begingroup$
    Because why you would? Even with just numbers, no functions: $1 < 2$, $3 < 4$ but $frac{1}{3} neq frac{2}{4}$. May be you wanted to write $frac{f}{g} leqslant frac{c_1}{c_2}$? It's still not true: you have $frac{1}{g} geqslant frac{1}{c_2 h}$, but you can multiply inequalities only with same direction.
    $endgroup$
    – mihaild
    17 hours ago






    1




    1




    $begingroup$
    Ok thank you. Now I see my mistake:)
    $endgroup$
    – Leon1998
    17 hours ago




    $begingroup$
    Ok thank you. Now I see my mistake:)
    $endgroup$
    – Leon1998
    17 hours ago











    7












    $begingroup$

    Consider $f(n)=h(n)=1$ and $g(n)=1/n$.






    share|cite|improve this answer









    $endgroup$


















      7












      $begingroup$

      Consider $f(n)=h(n)=1$ and $g(n)=1/n$.






      share|cite|improve this answer









      $endgroup$
















        7












        7








        7





        $begingroup$

        Consider $f(n)=h(n)=1$ and $g(n)=1/n$.






        share|cite|improve this answer









        $endgroup$



        Consider $f(n)=h(n)=1$ and $g(n)=1/n$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 17 hours ago









        FredFred

        48.7k11849




        48.7k11849






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            -

            Popular posts from this blog

            Why do type traits not work with types in namespace scope?What are POD types in C++?Why can templates only be...

            Image
            What does it mean to express a gate in Dirac notation? A Strange Latex Symbol How can Republicans who favour free markets, consistently express anger when they don't like the outcome of that choice? What happened to Captain America in Endgame? How to solve constants out of the internal energy equation? How can I place the product on a social media post better? Will tsunami waves travel forever if there was no land? Unexpected email from Yorkshire Bank What is the relationship between spectral sequences and obstruction theory? How can I practically buy stocks? Will a top journal at least re...
            Read more

            Will tsunami waves travel forever if there was no land?Why do tsunami waves begin with the water flowing away...

            Image
            How much cash can I safely carry into the USA and avoid civil forfeiture? Is there really no use for MD5 anymore? Is contacting this expert in the field something acceptable or would it be discourteous? How to pronounce 'C++' in Spanish How to creep the reader out with what seems like a normal person? Critique of timeline aesthetic Sci fi novel series with instant travel between planets through gates. A river runs through the gates How did Captain America manage to do this? Are Boeing 737-800’s grounded? Error message with tabularx How to make a pipeline wait for end-of-file or stop af...
            Read more

            Simple Scan not detecting my scanner (Brother DCP-7055W)Brother MFC-L2700DW printer can print, can't...

            Image
            Can someone publish a story that happened to you? Will tsunami waves travel forever if there was no land? What is the strongest case that can be made in favour of the UK regaining some control over fishing policy after Brexit? Controversial area of mathematics Packing rectangles: Does rotation ever help? Is there a way to get a compiler for the original B programming language? Using a Lyapunov function to classify stability and sketching a phase portrait Do I have an "anti-research" personality? Reducing vertical space in stackrel What does KSP mean? Pulling the rope with one hand is...
            Read more