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;
Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1
This is what I did:
- 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.
- 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
edited Mar 11 at 0:08
Asaf Rosemarin
418312
asked Mar 8 at 23:59
DCSDCS
445
add a comment |
Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1
This is what I did:
- 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.
- 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
edited Mar 11 at 0:08
Asaf Rosemarin
418312
asked Mar 8 at 23:59
DCSDCS
445
1
You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the2nterm. 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 is5n^2 + 2n -1 < C n^2wheren > n0for someCand somen0. 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 - 1is less or equal tof1(n), andf1(n)is less or equal tof2(n), and ...fj(n)is less or equal toCn^2. For some C and alln >= 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
add a comment |
Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1
This is what I did:
- 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.
- 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
edited Mar 11 at 0:08
Asaf Rosemarin
418312
asked Mar 8 at 23:59
DCSDCS
445
Exercise: Prove that 5nˆ2 + 2n - 1 is O(nˆ2) for n >= 1
This is what I did:
- 5nˆ2 + 2n - 1 < 5nˆ2 + 2n.
- 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
time-complexity big-o
edited Mar 11 at 0:08
Asaf Rosemarin
418312
asked Mar 8 at 23:59
DCSDCS
445
edited Mar 11 at 0:08
Asaf Rosemarin
418312
asked Mar 8 at 23:59
DCSDCS
445
edited Mar 11 at 0:08
Asaf Rosemarin
418312
edited Mar 11 at 0:08
Asaf Rosemarin
418312
edited Mar 11 at 0:08
Asaf Rosemarin
418312
418312
asked Mar 8 at 23:59
DCSDCS
445
asked Mar 8 at 23:59
DCSDCS
445
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" the2nterm. 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 is5n^2 + 2n -1 < C n^2wheren > n0for someCand somen0. 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 - 1is less or equal tof1(n), andf1(n)is less or equal tof2(n), and ...fj(n)is less or equal toCn^2. For some C and alln >= 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
add a comment |
1
You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the2nterm. 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 is5n^2 + 2n -1 < C n^2wheren > n0for someCand somen0. 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 - 1is less or equal tof1(n), andf1(n)is less or equal tof2(n), and ...fj(n)is less or equal toCn^2. For some C and alln >= 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
add a comment |
1 Answer
1
active
oldest
votes
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).
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
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%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
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).
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
add a comment |
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).
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
add a comment |
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).
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
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).
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
answered Mar 10 at 11:36
Asaf RosemarinAsaf Rosemarin
418312
418312
add a comment |
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%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
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
1
You are correct to be nervous. There is a logical disconnect between the 1st and 2nd steps. You have somehow "lost" the
2nterm. 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^2wheren > n0for someCand somen0. 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 - 1is less or equal tof1(n), andf1(n)is less or equal tof2(n), and ...fj(n)is less or equal toCn^2. For some C and alln >= 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