Dtjytyk

can i play a electric guitar through a bass amp?

Font hinting is lost in Chrome-like browsers (for some languages )

tikz: show 0 at the axis origin

Watching something be written to a file live with tail

Why don't electron-positron collisions release infinite energy?

How to write a macro that is braces sensitive?

What is the word for reserving something for yourself before others do?

Can divisibility rules for digits be generalized to sum of digits

Theorems that impeded progress

To string or not to string

Why was the small council so happy for Tyrion to become the Master of Coin?

How to find program name(s) of an installed package?

What are the differences between the usage of 'it' and 'they'?

Why can't I see bouncing of a switch on an oscilloscope?

How does strength of boric acid solution increase in presence of salicylic acid?

Can I make popcorn with any corn?

How old can references or sources in a thesis be?

Which models of the Boeing 737 are still in production?

How to format long polynomial?

Mathematical cryptic clues

Email Account under attack (really) - anything I can do?

I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine

How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?

Why does Kotter return in Welcome Back Kotter?

Show if $n sqrt n in O(n^4)$

Question about $i$Let p1, p2, ..pk be prime integers. if n = p1p2…pk + 1 then for every i, i =1, 2…,k, pi does not divide n.How to model 3 glass problem to graph?Show that if $a > 0$, then $ax^2 + bx + c ≥ 0$ for all values of $x$ if and only if $b^2 − 4ac ≤ 0$.An Intriguing Identity: $cos(2x) overset{?}{=} log_{cos(1)}frac{cos(cos(x))}{cos(sin(x))}$Proof that this algorithm calculates the “degrees of separation” in a graphLimits, roots, and exponents in an equationIs this proof correct? (Whitney's Theorem)analyzing worse case in a linear time selectionDo there exist whole number solutions to $27y + 23 = 32x$ and $81y + 85 = 128x$?

2

$begingroup$

I'm quite confused as to how to solve this step by step. What I have done was graph this using Desmos graphing software to visually see it, and I can see that the $n sqrt n $ is below $n^4$.

I thought I could do something like this:

$n sqrt n lt n^4$

$ sqrt n lt n^3$

$n^{1/2} lt n^4$

$1 lt n^4 / n^{1/2}$

$1 lt n^{7/2}$

So based on this, $n sqrt n$ is not bigO of $O(n^4)$. Is that correct? Or would I say it is BigO iff $n > 1$ ?

Thank you.

proof-verification algorithms

share|cite|improve this question

asked Mar 19 at 23:06

JamesWuJamesWu

184

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Remember for Big O, by definition you want to show that there exist constants $C$ and $n_0$ such that $nsqrt{n}le Cn^4$ for all $n> n_0$. Can you find such $C$ and $n_0$? You have done most of the work for it.
  $endgroup$
  – Minus One-Twelfth
  Mar 19 at 23:09
  
  
  

  
  
  
  

add a comment | 

2

$begingroup$

I'm quite confused as to how to solve this step by step. What I have done was graph this using Desmos graphing software to visually see it, and I can see that the $n sqrt n $ is below $n^4$.

I thought I could do something like this:

$n sqrt n lt n^4$

$ sqrt n lt n^3$

$n^{1/2} lt n^4$

$1 lt n^4 / n^{1/2}$

$1 lt n^{7/2}$

So based on this, $n sqrt n$ is not bigO of $O(n^4)$. Is that correct? Or would I say it is BigO iff $n > 1$ ?

Thank you.

proof-verification algorithms

share|cite|improve this question

asked Mar 19 at 23:06

JamesWuJamesWu

184

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Remember for Big O, by definition you want to show that there exist constants $C$ and $n_0$ such that $nsqrt{n}le Cn^4$ for all $n> n_0$. Can you find such $C$ and $n_0$? You have done most of the work for it.
  $endgroup$
  – Minus One-Twelfth
  Mar 19 at 23:09
  
  
  

  
  
  
  

add a comment | 

$begingroup$

I'm quite confused as to how to solve this step by step. What I have done was graph this using Desmos graphing software to visually see it, and I can see that the $n sqrt n $ is below $n^4$.

I thought I could do something like this:

$n sqrt n lt n^4$

$ sqrt n lt n^3$

$n^{1/2} lt n^4$

$1 lt n^4 / n^{1/2}$

$1 lt n^{7/2}$

So based on this, $n sqrt n$ is not bigO of $O(n^4)$. Is that correct? Or would I say it is BigO iff $n > 1$ ?

Thank you.

proof-verification algorithms

share|cite|improve this question

asked Mar 19 at 23:06

JamesWuJamesWu

184

$endgroup$

share|cite|improve this question

asked Mar 19 at 23:06

JamesWuJamesWu

184

share|cite|improve this question

asked Mar 19 at 23:06

JamesWuJamesWu

184

asked Mar 19 at 23:06

JamesWuJamesWu

184

asked Mar 19 at 23:06

JamesWuJamesWu

184

3 Answers
3

active

oldest

votes

2

$begingroup$

All boils down to $xge 1implies x^2ge x$ when multiplying both sides by $x$

For $nge 1$

• you have $sqrt{n}ge 1$ so $nge sqrt{n}$
  


• you have also $n^3ge n^2ge n$ by the same principle

Gathering everything gives you $n^3ge sqrt{n}$, which formally has $n_0=1$ and $C=1$ from the big-O notation:

$forall nge n_0$ then $sqrt{n}le Cn^3iff sqrt{n}=O(n^3)$

which is equivalent to $nsqrt{n}=O(n^4)$ as you noticed yourself.

share|cite|improve this answer

answered Mar 19 at 23:36

zwimzwim

12.7k832

$endgroup$

add a comment | 

0

$begingroup$

${{nsqrt n}over n^4}={1over n^{5/2}}$ and $lim_limits{nrightarrow +infty}{1over n^{5/2}}=0$.

share|cite|improve this answer

edited Mar 19 at 23:38

Robert Howard

2,3033935

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

$endgroup$

add a comment | 

-1

$begingroup$

Why make things more complex than they are? Very simply, $;nsqrt n=o(n^4)$, so a fortiori, it is $O(n^4)$.

This being said, how do you proceed from $sqrt n < n^3$ to $n^{1/2} < n^4$?

If you want to prove directly that $nsqrt n=O(n^4)$ (or not), you have to prove the ration $,frac{nsqrt n}{n^4}$ is bounded by some constant $C$ for all $n$ large enough, and this constant is not necessarily $1$.

share|cite|improve this answer

edited Mar 19 at 23:20

answered Mar 19 at 23:09

BernardBernard

124k741116

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This does obviously not address the OP's problem to understand the $O$-problematic. This is IMO no help at all.
  $endgroup$
  – Ingix
  Mar 19 at 23:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I will not make an answer just to ask how the O.P. goes from line 2 to line 3!
  $endgroup$
  – Bernard
  Mar 19 at 23:16
  

  
  
  
  

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%2f3154744%2fshow-if-n-sqrt-n-in-on4%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

All boils down to $xge 1implies x^2ge x$ when multiplying both sides by $x$

For $nge 1$

• you have $sqrt{n}ge 1$ so $nge sqrt{n}$
  


• you have also $n^3ge n^2ge n$ by the same principle

Gathering everything gives you $n^3ge sqrt{n}$, which formally has $n_0=1$ and $C=1$ from the big-O notation:

$forall nge n_0$ then $sqrt{n}le Cn^3iff sqrt{n}=O(n^3)$

which is equivalent to $nsqrt{n}=O(n^4)$ as you noticed yourself.

share|cite|improve this answer

answered Mar 19 at 23:36

zwimzwim

12.7k832

$endgroup$

add a comment | 

2

$begingroup$

All boils down to $xge 1implies x^2ge x$ when multiplying both sides by $x$

For $nge 1$

• you have $sqrt{n}ge 1$ so $nge sqrt{n}$
  


• you have also $n^3ge n^2ge n$ by the same principle

Gathering everything gives you $n^3ge sqrt{n}$, which formally has $n_0=1$ and $C=1$ from the big-O notation:

$forall nge n_0$ then $sqrt{n}le Cn^3iff sqrt{n}=O(n^3)$

which is equivalent to $nsqrt{n}=O(n^4)$ as you noticed yourself.

share|cite|improve this answer

answered Mar 19 at 23:36

zwimzwim

12.7k832

$endgroup$

add a comment | 

$begingroup$

All boils down to $xge 1implies x^2ge x$ when multiplying both sides by $x$

For $nge 1$

• you have $sqrt{n}ge 1$ so $nge sqrt{n}$
  


• you have also $n^3ge n^2ge n$ by the same principle

Gathering everything gives you $n^3ge sqrt{n}$, which formally has $n_0=1$ and $C=1$ from the big-O notation:

$forall nge n_0$ then $sqrt{n}le Cn^3iff sqrt{n}=O(n^3)$

which is equivalent to $nsqrt{n}=O(n^4)$ as you noticed yourself.

share|cite|improve this answer

answered Mar 19 at 23:36

zwimzwim

12.7k832

$endgroup$

share|cite|improve this answer

answered Mar 19 at 23:36

zwimzwim

12.7k832

answered Mar 19 at 23:36

zwimzwim

12.7k832

answered Mar 19 at 23:36

zwimzwim

12.7k832

0

$begingroup$

${{nsqrt n}over n^4}={1over n^{5/2}}$ and $lim_limits{nrightarrow +infty}{1over n^{5/2}}=0$.

share|cite|improve this answer

edited Mar 19 at 23:38

Robert Howard

2,3033935

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

$endgroup$

add a comment | 

0

$begingroup$

${{nsqrt n}over n^4}={1over n^{5/2}}$ and $lim_limits{nrightarrow +infty}{1over n^{5/2}}=0$.

share|cite|improve this answer

edited Mar 19 at 23:38

Robert Howard

2,3033935

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

$endgroup$

add a comment | 

$begingroup$

${{nsqrt n}over n^4}={1over n^{5/2}}$ and $lim_limits{nrightarrow +infty}{1over n^{5/2}}=0$.

share|cite|improve this answer

edited Mar 19 at 23:38

Robert Howard

2,3033935

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

$endgroup$

share|cite|improve this answer

edited Mar 19 at 23:38

Robert Howard

2,3033935

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

edited Mar 19 at 23:38

Robert Howard

2,3033935

edited Mar 19 at 23:38

Robert Howard

2,3033935

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

answered Mar 19 at 23:11

Tsemo AristideTsemo Aristide

60.2k11446

-1

$begingroup$

Why make things more complex than they are? Very simply, $;nsqrt n=o(n^4)$, so a fortiori, it is $O(n^4)$.

This being said, how do you proceed from $sqrt n < n^3$ to $n^{1/2} < n^4$?

If you want to prove directly that $nsqrt n=O(n^4)$ (or not), you have to prove the ration $,frac{nsqrt n}{n^4}$ is bounded by some constant $C$ for all $n$ large enough, and this constant is not necessarily $1$.

share|cite|improve this answer

edited Mar 19 at 23:20

answered Mar 19 at 23:09

BernardBernard

124k741116

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This does obviously not address the OP's problem to understand the $O$-problematic. This is IMO no help at all.
  $endgroup$
  – Ingix
  Mar 19 at 23:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I will not make an answer just to ask how the O.P. goes from line 2 to line 3!
  $endgroup$
  – Bernard
  Mar 19 at 23:16
  

  
  
  
  

add a comment | 

-1

$begingroup$

Why make things more complex than they are? Very simply, $;nsqrt n=o(n^4)$, so a fortiori, it is $O(n^4)$.

This being said, how do you proceed from $sqrt n < n^3$ to $n^{1/2} < n^4$?

If you want to prove directly that $nsqrt n=O(n^4)$ (or not), you have to prove the ration $,frac{nsqrt n}{n^4}$ is bounded by some constant $C$ for all $n$ large enough, and this constant is not necessarily $1$.

share|cite|improve this answer

edited Mar 19 at 23:20

answered Mar 19 at 23:09

BernardBernard

124k741116

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This does obviously not address the OP's problem to understand the $O$-problematic. This is IMO no help at all.
  $endgroup$
  – Ingix
  Mar 19 at 23:11
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I will not make an answer just to ask how the O.P. goes from line 2 to line 3!
  $endgroup$
  – Bernard
  Mar 19 at 23:16
  

  
  
  
  

add a comment | 

$begingroup$

Why make things more complex than they are? Very simply, $;nsqrt n=o(n^4)$, so a fortiori, it is $O(n^4)$.

This being said, how do you proceed from $sqrt n < n^3$ to $n^{1/2} < n^4$?

If you want to prove directly that $nsqrt n=O(n^4)$ (or not), you have to prove the ration $,frac{nsqrt n}{n^4}$ is bounded by some constant $C$ for all $n$ large enough, and this constant is not necessarily $1$.

share|cite|improve this answer

edited Mar 19 at 23:20

answered Mar 19 at 23:09

BernardBernard

124k741116

$endgroup$

share|cite|improve this answer

edited Mar 19 at 23:20

answered Mar 19 at 23:09

BernardBernard

124k741116

answered Mar 19 at 23:09

BernardBernard

124k741116

answered Mar 19 at 23:09

BernardBernard

124k741116