How to prove using big-OBig O, how do you calculate/approximate it?What is a plain English explanation of “Big O” notation?Whats the least upper bound of the growth rate using big-Oh notation of these two functionsHow to prove big-o relationsProving and Disproving BigOhow do you prove that the big theta of a series is its leading term?Big O proof with sqrt and logDetermining complexity for recursive functions (Big O notation)Proving Big theta for polynomials using quantificational definitionIs any function Big-O itself?
How is the problem, G has no triangle in Logspace?
Aligning two sets of equations with alignat?
What informations can we obtain with these voltage and current measurements of a little electronic device?
Writing a letter of recommendation for a mediocre student
Paradox regarding phase transitions in relativistic systems
US entry with tourist visa but past alcohol arrest
Cheap antenna for new HF HAM
pandas aggregate with dynamic column names
Should the pagination be reset when changing the order?
What is the need of methods like GET and POST in the HTTP protocol?
Is Zack Morris's 'time stop' ability in "Saved By the Bell" a supernatural ability?
Is it really necessary to have 4 hours meeting in Sprint planning?
Simulate a 1D Game-of-Life-ish Model
CDG baggage claim before or after immigration?
What was an "insurance cover"?
Do liquid propellant rocket engines experience thrust oscillation?
Create a magic square of 4-digit numbers
How do I clean sealant/silicon from a glass mirror?
In a jam session, when asked which key my non-transposing instrument (like a violin) is in, what do I answer?
How to influence manager to not schedule team meetings during lunch?
Can someone explain to me the parameters of a lognormal distribution?
Сardinality estimation of partially covering range predicates
Was there a trial by combat between a man and a dog in medieval France?
Is there any reason nowadays to use a neon indicator lamp instead of an LED?
How to prove using big-O
Big O, how do you calculate/approximate it?What is a plain English explanation of “Big O” notation?Whats the least upper bound of the growth rate using big-Oh notation of these two functionsHow to prove big-o relationsProving and Disproving BigOhow do you prove that the big theta of a series is its leading term?Big O proof with sqrt and logDetermining complexity for recursive functions (Big O notation)Proving Big theta for polynomials using quantificational definitionIs any function Big-O itself?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
Im currently having a problem with big O notation. I have the following question which I am trying to figure out.
I currently have the formula: T(n) is O(f(n)) and I must use this to prove directly from the definition of big O that 3n^2+11n+6 is O(n^2).
I was wondering if anybody could possibly help me figure out this problem as I am having trouble working it out.
big-o
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
add a comment
|
Im currently having a problem with big O notation. I have the following question which I am trying to figure out.
I currently have the formula: T(n) is O(f(n)) and I must use this to prove directly from the definition of big O that 3n^2+11n+6 is O(n^2).
I was wondering if anybody could possibly help me figure out this problem as I am having trouble working it out.
big-o
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
You should already know the mathematical definition of big-O.
– meowgoesthedog
Mar 28 at 15:14
Yes I know the mathematical definition of big O already which is T(n) <= Cxf(n) for all values of n >= N. However I am unsure on how to use this to prove the problem above
– Virdee
Mar 28 at 15:21
add a comment
|
Im currently having a problem with big O notation. I have the following question which I am trying to figure out.
I currently have the formula: T(n) is O(f(n)) and I must use this to prove directly from the definition of big O that 3n^2+11n+6 is O(n^2).
I was wondering if anybody could possibly help me figure out this problem as I am having trouble working it out.
big-o
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
Im currently having a problem with big O notation. I have the following question which I am trying to figure out.
I currently have the formula: T(n) is O(f(n)) and I must use this to prove directly from the definition of big O that 3n^2+11n+6 is O(n^2).
I was wondering if anybody could possibly help me figure out this problem as I am having trouble working it out.
big-o
big-o
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
asked Mar 28 at 14:57
VirdeeVirdee
125 bronze badges
125 bronze badges
You should already know the mathematical definition of big-O.
– meowgoesthedog
Mar 28 at 15:14
Yes I know the mathematical definition of big O already which is T(n) <= Cxf(n) for all values of n >= N. However I am unsure on how to use this to prove the problem above
– Virdee
Mar 28 at 15:21
add a comment
|
You should already know the mathematical definition of big-O.
– meowgoesthedog
Mar 28 at 15:14
Yes I know the mathematical definition of big O already which is T(n) <= Cxf(n) for all values of n >= N. However I am unsure on how to use this to prove the problem above
– Virdee
Mar 28 at 15:21
You should already know the mathematical definition of big-O.
– meowgoesthedog
Mar 28 at 15:14
You should already know the mathematical definition of big-O.
– meowgoesthedog
Mar 28 at 15:14
Yes I know the mathematical definition of big O already which is T(n) <= Cxf(n) for all values of n >= N. However I am unsure on how to use this to prove the problem above
– Virdee
Mar 28 at 15:21
Yes I know the mathematical definition of big O already which is T(n) <= Cxf(n) for all values of n >= N. However I am unsure on how to use this to prove the problem above
– Virdee
Mar 28 at 15:21
add a comment
|
1 Answer
1
active
oldest
votes
I think this may help:
For n≥k, there is a constant, let's name it "c" which satisfies 3n^2 + 11n + 6 ≤ c∗n^2.
Let's say we pick k = 1.
We know that n^2 ≥ n^2 ≥ n ≥ 1
So :3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2
Now, let c = 20.
=>complexity is O(n2).
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
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/4.0/"u003ecc by-sa 4.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%2f55400747%2fhow-to-prove-using-big-o%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
I think this may help:
For n≥k, there is a constant, let's name it "c" which satisfies 3n^2 + 11n + 6 ≤ c∗n^2.
Let's say we pick k = 1.
We know that n^2 ≥ n^2 ≥ n ≥ 1
So :3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2
Now, let c = 20.
=>complexity is O(n2).
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
add a comment
|
I think this may help:
For n≥k, there is a constant, let's name it "c" which satisfies 3n^2 + 11n + 6 ≤ c∗n^2.
Let's say we pick k = 1.
We know that n^2 ≥ n^2 ≥ n ≥ 1
So :3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2
Now, let c = 20.
=>complexity is O(n2).
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
add a comment
|
I think this may help:
For n≥k, there is a constant, let's name it "c" which satisfies 3n^2 + 11n + 6 ≤ c∗n^2.
Let's say we pick k = 1.
We know that n^2 ≥ n^2 ≥ n ≥ 1
So :3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2
Now, let c = 20.
=>complexity is O(n2).
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
I think this may help:
For n≥k, there is a constant, let's name it "c" which satisfies 3n^2 + 11n + 6 ≤ c∗n^2.
Let's say we pick k = 1.
We know that n^2 ≥ n^2 ≥ n ≥ 1
So :3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2
Now, let c = 20.
=>complexity is O(n2).
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
answered Mar 28 at 15:23
Theodor BadeaTheodor Badea
3156 bronze badges
3156 bronze badges
add a comment
|
add a comment
|
Got a question that you can’t ask on public Stack Overflow? Learn more about sharing private information with Stack Overflow for Teams.
Got a question that you can’t ask on public Stack Overflow? Learn more about sharing private information with Stack Overflow for Teams.
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%2f55400747%2fhow-to-prove-using-big-o%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
You should already know the mathematical definition of big-O.
– meowgoesthedog
Mar 28 at 15:14
Yes I know the mathematical definition of big O already which is T(n) <= Cxf(n) for all values of n >= N. However I am unsure on how to use this to prove the problem above
– Virdee
Mar 28 at 15:21