Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1proving n^k = Ω(c^n)Prove f(n) + g(n) is O(max(f(n),g(n)))If, g , h are functions such that f(n) = O(g(n)) and g(n) = O(h(n)) prove f(n) = O(h(n))Practical difference between O(n) and O(1 + n)?If a>=b then O(a+b)=O(a)?Analyze big O relation between 5^(log2N) and N^(1/2), and how to prove it?Big-O notation proveWhat's the upper bound of f(n) = n^4 + 100n^2 + 50?Prove f(n) + d(n)= O(g(n)+ h(n))Am I Oversimplifying Calculating Complexity

Why can't we play rap on piano?

Has there ever been an airliner design involving reducing generator load by installing solar panels?

Can one be a co-translator of a book, if he does not know the language that the book is translated into?

I'm flying to France today and my passport expires in less than 2 months

Why does Kotter return in Welcome Back Kotter?

Why does Arabsat 6A need a Falcon Heavy to launch

What to put in ESTA if staying in US for a few days before going on to Canada

Anagram holiday

Why do bosons tend to occupy the same state?

Brothers & sisters

Today is the Center

Would Slavery Reparations be considered Bills of Attainder and hence Illegal?

Why are electrically insulating heatsinks so rare? Is it just cost?

90's TV series where a boy goes to another dimension through portal near power lines

What is the intuition behind short exact sequences of groups; in particular, what is the intuition behind group extensions?

Arrow those variables!

Does a druid starting with a bow start with no arrows?

Were any external disk drives stacked vertically?

Facing a paradox: Earnshaw's theorem in one dimension

Is it unprofessional to ask if a job posting on GlassDoor is real?

How much of data wrangling is a data scientist's job?

If human space travel is limited by the G force vulnerability, is there a way to counter G forces?

CEO ridiculed me with gay jokes and grabbed me and wouldn't let go - now getting pushed out of company

Western buddy movie with a supernatural twist where a woman turns into an eagle at the end



Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1


proving n^k = Ω(c^n)Prove f(n) + g(n) is O(max(f(n),g(n)))If, g , h are functions such that f(n) = O(g(n)) and g(n) = O(h(n)) prove f(n) = O(h(n))Practical difference between O(n) and O(1 + n)?If a>=b then O(a+b)=O(a)?Analyze big O relation between 5^(log2N) and N^(1/2), and how to prove it?Big-O notation proveWhat's the upper bound of f(n) = n^4 + 100n^2 + 50?Prove f(n) + d(n)= O(g(n)+ h(n))Am I Oversimplifying Calculating Complexity






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;








-2















Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1



This is what I did:




  1. 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.

  2. 5nˆ2 - 1 < 5nˆ2



this means that C= 5 and n0 = 1



I'm a bit nervous because I feel this was too simple of a procedure. Did I do something wrong or is this alright?



Thanks!










share|improve this question



















  • 1





    You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the 2n term. Try again.

    – Stephen C
    Mar 9 at 0:47












  • @StephenC I subtracted it from both sides, was I wrong to do so?

    – DCS
    Mar 9 at 2:08







  • 2





    Yea. Subtracting a term on both sides of an inequality is mathematically sound ... but it doesn't help you prove what you need to prove. What you need to establish is 5n^2 + 2n -1 < C n^2 where n > n0 for some C and some n0. Your transformations don't prove that.

    – Stephen C
    Mar 9 at 2:17







  • 2





    Your approach should be to prove a chain like this: 5nˆ2 + 2n - 1 is less or equal to f1(n), and f1(n) is less or equal to f2(n), and ... fj(n) is less or equal to Cn^2. For some C and all n >= n0.

    – Stephen C
    Mar 9 at 2:21











  • Questions about theoretical computer science are a better fit for Computer Science

    – Charles Duffy
    Mar 11 at 0:50

















-2















Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1



This is what I did:




  1. 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.

  2. 5nˆ2 - 1 < 5nˆ2



this means that C= 5 and n0 = 1



I'm a bit nervous because I feel this was too simple of a procedure. Did I do something wrong or is this alright?



Thanks!










share|improve this question



















  • 1





    You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the 2n term. Try again.

    – Stephen C
    Mar 9 at 0:47












  • @StephenC I subtracted it from both sides, was I wrong to do so?

    – DCS
    Mar 9 at 2:08







  • 2





    Yea. Subtracting a term on both sides of an inequality is mathematically sound ... but it doesn't help you prove what you need to prove. What you need to establish is 5n^2 + 2n -1 < C n^2 where n > n0 for some C and some n0. Your transformations don't prove that.

    – Stephen C
    Mar 9 at 2:17







  • 2





    Your approach should be to prove a chain like this: 5nˆ2 + 2n - 1 is less or equal to f1(n), and f1(n) is less or equal to f2(n), and ... fj(n) is less or equal to Cn^2. For some C and all n >= n0.

    – Stephen C
    Mar 9 at 2:21











  • Questions about theoretical computer science are a better fit for Computer Science

    – Charles Duffy
    Mar 11 at 0:50













-2












-2








-2








Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1



This is what I did:




  1. 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.

  2. 5nˆ2 - 1 < 5nˆ2



this means that C= 5 and n0 = 1



I'm a bit nervous because I feel this was too simple of a procedure. Did I do something wrong or is this alright?



Thanks!










share|improve this question
















Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1



This is what I did:




  1. 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.

  2. 5nˆ2 - 1 < 5nˆ2



this means that C= 5 and n0 = 1



I'm a bit nervous because I feel this was too simple of a procedure. Did I do something wrong or is this alright?



Thanks!







time-complexity big-o






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Mar 11 at 0:08









Asaf Rosemarin

418312




418312










asked Mar 8 at 23:59









DCSDCS

445




445







  • 1





    You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the 2n term. Try again.

    – Stephen C
    Mar 9 at 0:47












  • @StephenC I subtracted it from both sides, was I wrong to do so?

    – DCS
    Mar 9 at 2:08







  • 2





    Yea. Subtracting a term on both sides of an inequality is mathematically sound ... but it doesn't help you prove what you need to prove. What you need to establish is 5n^2 + 2n -1 < C n^2 where n > n0 for some C and some n0. Your transformations don't prove that.

    – Stephen C
    Mar 9 at 2:17







  • 2





    Your approach should be to prove a chain like this: 5nˆ2 + 2n - 1 is less or equal to f1(n), and f1(n) is less or equal to f2(n), and ... fj(n) is less or equal to Cn^2. For some C and all n >= n0.

    – Stephen C
    Mar 9 at 2:21











  • Questions about theoretical computer science are a better fit for Computer Science

    – Charles Duffy
    Mar 11 at 0:50












  • 1





    You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the 2n term. Try again.

    – Stephen C
    Mar 9 at 0:47












  • @StephenC I subtracted it from both sides, was I wrong to do so?

    – DCS
    Mar 9 at 2:08







  • 2





    Yea. Subtracting a term on both sides of an inequality is mathematically sound ... but it doesn't help you prove what you need to prove. What you need to establish is 5n^2 + 2n -1 < C n^2 where n > n0 for some C and some n0. Your transformations don't prove that.

    – Stephen C
    Mar 9 at 2:17







  • 2





    Your approach should be to prove a chain like this: 5nˆ2 + 2n - 1 is less or equal to f1(n), and f1(n) is less or equal to f2(n), and ... fj(n) is less or equal to Cn^2. For some C and all n >= n0.

    – Stephen C
    Mar 9 at 2:21











  • Questions about theoretical computer science are a better fit for Computer Science

    – Charles Duffy
    Mar 11 at 0:50







1




1





You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the 2n term. Try again.

– Stephen C
Mar 9 at 0:47






You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the 2n term. Try again.

– Stephen C
Mar 9 at 0:47














@StephenC I subtracted it from both sides, was I wrong to do so?

– DCS
Mar 9 at 2:08






@StephenC I subtracted it from both sides, was I wrong to do so?

– DCS
Mar 9 at 2:08





2




2





Yea. Subtracting a term on both sides of an inequality is mathematically sound ... but it doesn't help you prove what you need to prove. What you need to establish is 5n^2 + 2n -1 < C n^2 where n > n0 for some C and some n0. Your transformations don't prove that.

– Stephen C
Mar 9 at 2:17






Yea. Subtracting a term on both sides of an inequality is mathematically sound ... but it doesn't help you prove what you need to prove. What you need to establish is 5n^2 + 2n -1 < C n^2 where n > n0 for some C and some n0. Your transformations don't prove that.

– Stephen C
Mar 9 at 2:17





2




2





Your approach should be to prove a chain like this: 5nˆ2 + 2n - 1 is less or equal to f1(n), and f1(n) is less or equal to f2(n), and ... fj(n) is less or equal to Cn^2. For some C and all n >= n0.

– Stephen C
Mar 9 at 2:21





Your approach should be to prove a chain like this: 5nˆ2 + 2n - 1 is less or equal to f1(n), and f1(n) is less or equal to f2(n), and ... fj(n) is less or equal to Cn^2. For some C and all n >= n0.

– Stephen C
Mar 9 at 2:21













Questions about theoretical computer science are a better fit for Computer Science

– Charles Duffy
Mar 11 at 0:50





Questions about theoretical computer science are a better fit for Computer Science

– Charles Duffy
Mar 11 at 0:50












1 Answer
1






active

oldest

votes


















2














First of all, big O notation regards asymptotic growth, so the n >= 1 is actually redundant.

By the definition of big O, f(n) = O(g(n)) if there exists some c, n0 > 0 s.t. for all n > n0 it holds that f(n) <= cg(n).

So in our case: 5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2 as for every natural integer it holds that n^2 >= n.

Choose c = 7, n0 = 1 and for all n > n0 we get that 5n^2 + 2n -1 <= 7n^2 = cn^2.

Conculsion: 5n^2 + 2n - 1 = O(n^2).






share|improve this answer























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



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55072615%2fprove-that-5n%25cb%25862-2n-1-is-on%25cb%25862-for-n-1%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









    2














    First of all, big O notation regards asymptotic growth, so the n >= 1 is actually redundant.

    By the definition of big O, f(n) = O(g(n)) if there exists some c, n0 > 0 s.t. for all n > n0 it holds that f(n) <= cg(n).

    So in our case: 5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2 as for every natural integer it holds that n^2 >= n.

    Choose c = 7, n0 = 1 and for all n > n0 we get that 5n^2 + 2n -1 <= 7n^2 = cn^2.

    Conculsion: 5n^2 + 2n - 1 = O(n^2).






    share|improve this answer



























      2














      First of all, big O notation regards asymptotic growth, so the n >= 1 is actually redundant.

      By the definition of big O, f(n) = O(g(n)) if there exists some c, n0 > 0 s.t. for all n > n0 it holds that f(n) <= cg(n).

      So in our case: 5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2 as for every natural integer it holds that n^2 >= n.

      Choose c = 7, n0 = 1 and for all n > n0 we get that 5n^2 + 2n -1 <= 7n^2 = cn^2.

      Conculsion: 5n^2 + 2n - 1 = O(n^2).






      share|improve this answer

























        2












        2








        2







        First of all, big O notation regards asymptotic growth, so the n >= 1 is actually redundant.

        By the definition of big O, f(n) = O(g(n)) if there exists some c, n0 > 0 s.t. for all n > n0 it holds that f(n) <= cg(n).

        So in our case: 5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2 as for every natural integer it holds that n^2 >= n.

        Choose c = 7, n0 = 1 and for all n > n0 we get that 5n^2 + 2n -1 <= 7n^2 = cn^2.

        Conculsion: 5n^2 + 2n - 1 = O(n^2).






        share|improve this answer













        First of all, big O notation regards asymptotic growth, so the n >= 1 is actually redundant.

        By the definition of big O, f(n) = O(g(n)) if there exists some c, n0 > 0 s.t. for all n > n0 it holds that f(n) <= cg(n).

        So in our case: 5n^2 + 2n - 1 <= 5n^2 + 2n <= 5n^2 + 2n^2 = 7n^2 as for every natural integer it holds that n^2 >= n.

        Choose c = 7, n0 = 1 and for all n > n0 we get that 5n^2 + 2n -1 <= 7n^2 = cn^2.

        Conculsion: 5n^2 + 2n - 1 = O(n^2).







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Mar 10 at 11:36









        Asaf RosemarinAsaf Rosemarin

        418312




        418312





























            draft saved

            draft discarded
















































            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.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55072615%2fprove-that-5n%25cb%25862-2n-1-is-on%25cb%25862-for-n-1%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

            Identity Server 4 is not redirecting to Angular app after login2019 Community Moderator ElectionIdentity Server 4 and dockerIdentityserver implicit flow unauthorized_clientIdentityServer Hybrid Flow - Access Token is null after user successful loginIdentity Server to MVC client : Page Redirect After loginLogin with Steam OpenId(oidc-client-js)Identity Server 4+.NET Core 2.0 + IdentityIdentityServer4 post-login redirect not working in Edge browserCall to IdentityServer4 generates System.NullReferenceException: Object reference not set to an instance of an objectIdentityServer4 without HTTPS not workingHow to get Authorization code from identity server without login form

            2005 Ahvaz unrest Contents Background Causes Casualties Aftermath See also References Navigation menue"At Least 10 Are Killed by Bombs in Iran""Iran"Archived"Arab-Iranians in Iran to make April 15 'Day of Fury'"State of Mind, State of Order: Reactions to Ethnic Unrest in the Islamic Republic of Iran.10.1111/j.1754-9469.2008.00028.x"Iran hangs Arab separatists"Iran Overview from ArchivedConstitution of the Islamic Republic of Iran"Tehran puzzled by forged 'riots' letter""Iran and its minorities: Down in the second class""Iran: Handling Of Ahvaz Unrest Could End With Televised Confessions""Bombings Rock Iran Ahead of Election""Five die in Iran ethnic clashes""Iran: Need for restraint as anniversary of unrest in Khuzestan approaches"Archived"Iranian Sunni protesters killed in clashes with security forces"Archived

            Can't initialize raids on a new ASUS Prime B360M-A motherboard2019 Community Moderator ElectionSimilar to RAID config yet more like mirroring solution?Can't get motherboard serial numberWhy does the BIOS entry point start with a WBINVD instruction?UEFI performance Asus Maximus V Extreme