Fdtxjr

Are Warlocks Arcane or Divine?

Why does this part of the Space Shuttle launch pad seem to be floating in air?

Teaching indefinite integrals that require special-casing

Why isn't KTEX's runway designation 10/28 instead of 9/27?

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?

Reply ‘no position’ while the job posting is still there (‘HiWi’ position in Germany)

How can I raise concerns with a new DM about XP splitting?

Can a malicious addon access internet history and such in chrome/firefox?

Adding empty element to declared container without declaring type of element

Perfect riffle shuffles

Is there any significance to the Valyrian Stone vault door of Qarth?

A workplace installs custom certificates on personal devices, can this be used to decrypt HTTPS traffic?

Lifted its hind leg on or lifted its hind leg towards?

Why are on-board computers allowed to change controls without notifying the pilots?

Is it legal to discriminate due to the medicine used to treat a medical condition?

My boss asked me to take a one-day class, then signs it up as a day off

Is a naturally all "male" species possible?

Can a controlled ghast be a leader of a pack of ghouls?

Are taller landing gear bad for aircraft, particulary large airliners?

Should my PhD thesis be submitted under my legal name?

How will losing mobility of one hand affect my career as a programmer?

Indicating multiple different modes of speech (fantasy language or telepathy)

Blender - show edges angles “direction”

Did US corporations pay demonstrators in the German demonstrations against article 13?

How to solve basic asymptotic algorithm problem [closed]

Asymptotic analysis of a recurring sequencehow to show the convergence of an algorithmasymptotic estimate for this expressionUniform asymptotic expansionAsymptotic behaviour of a sumA question regarding the order of an asymptotic estimateApplication of algorithm to sequenceSimple asymptotic analysis problemBasic Rule of Stochastic Orders/Asymptotic NotationAsymptotic Problem Complexity = Infimum of Asymptotic Algorithm Complexities?

-1

$begingroup$

beginequation
f(n) = n-100\
g(n) = n-200
endequation
How can I prove that $f(n) = O(g(n))$ or $f(n) = Ω(g(n))$?

algorithms asymptotics

share|cite|improve this question

edited Mar 16 at 21:11

MarianD

1,5911617

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

$endgroup$

closed as off-topic by Yanko, mrtaurho, John Omielan, YiFan, RRL Mar 17 at 0:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Yanko, mrtaurho, John Omielan, YiFan, RRL

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you familiar with the definitions of $O$ and $Omega$? For example for the $O$, you effectively want to show that there exist $n_0$ and $C$ such that $n-100 le C(n-200)$ for all $n > n_0$. Can you do this?
  $endgroup$
  – Minus One-Twelfth
  Mar 16 at 20:59
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes I know the theory but I am not sure how to use it
  $endgroup$
  – Konstantinos Kyriakos
  Mar 16 at 21:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Have you made any progress on finding such $n_0$ and $C$? And do you have any examples in your textbook/notes that you could see as a guide?
  $endgroup$
  – Minus One-Twelfth
  Mar 16 at 21:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  No I don't have any example to understand the steps to prove something like that. I was thinking something about n-100 <= c(n-200) --> n(c-1) - 100(c-2) >= 0 but i am stuck
  $endgroup$
  – Konstantinos Kyriakos
  Mar 16 at 21:10
  

  
  
  
  

add a comment | 

-1

$begingroup$

beginequation
f(n) = n-100\
g(n) = n-200
endequation
How can I prove that $f(n) = O(g(n))$ or $f(n) = Ω(g(n))$?

algorithms asymptotics

share|cite|improve this question

edited Mar 16 at 21:11

MarianD

1,5911617

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

$endgroup$

closed as off-topic by Yanko, mrtaurho, John Omielan, YiFan, RRL Mar 17 at 0:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Yanko, mrtaurho, John Omielan, YiFan, RRL

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you familiar with the definitions of $O$ and $Omega$? For example for the $O$, you effectively want to show that there exist $n_0$ and $C$ such that $n-100 le C(n-200)$ for all $n > n_0$. Can you do this?
  $endgroup$
  – Minus One-Twelfth
  Mar 16 at 20:59
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes I know the theory but I am not sure how to use it
  $endgroup$
  – Konstantinos Kyriakos
  Mar 16 at 21:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Have you made any progress on finding such $n_0$ and $C$? And do you have any examples in your textbook/notes that you could see as a guide?
  $endgroup$
  – Minus One-Twelfth
  Mar 16 at 21:03
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  No I don't have any example to understand the steps to prove something like that. I was thinking something about n-100 <= c(n-200) --> n(c-1) - 100(c-2) >= 0 but i am stuck
  $endgroup$
  – Konstantinos Kyriakos
  Mar 16 at 21:10
  

  
  
  
  

add a comment | 

$begingroup$

beginequation
f(n) = n-100\
g(n) = n-200
endequation
How can I prove that $f(n) = O(g(n))$ or $f(n) = Ω(g(n))$?

algorithms asymptotics

share|cite|improve this question

edited Mar 16 at 21:11

MarianD

1,5911617

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

$endgroup$

share|cite|improve this question

edited Mar 16 at 21:11

MarianD

1,5911617

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

share|cite|improve this question

edited Mar 16 at 21:11

MarianD

1,5911617

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

edited Mar 16 at 21:11

MarianD

1,5911617

edited Mar 16 at 21:11

MarianD

1,5911617

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

asked Mar 16 at 20:58

Konstantinos KyriakosKonstantinos Kyriakos

32

1 Answer
1

active

oldest

votes

0

$begingroup$

Well, the first thing I notice as I look at this situation is that $f(n)$ and $g(n)$ are negative initially. We're going to want them to be positive, at least, for otherwise, $Ccdot g(n)<f(n)$ for any positive $C.$ Thus, we only need to consider $n>200.$

Now, in the comments, you pointed out that you'd gotten from $$n-100le Ccdot(n-200)$$ to the statement $$ncdot(C-1)-100(C-2)ge 0.$$ Unfortunately, something appears to have gone wrong. Let me take you through the steps. $$n-100le Ccdot(n-200)\n-100le Cn-200C\-100le Cn-n-200C\-100le ncdot(C-1)-200 C\0le ncdot(C-1)+100-200 C\0le ncdot(C-1)+100(1-2C).$$

At this point, you're basically there! Let's rewrite it instead as $$ncdot(C-1)ge100cdot(2C-1),$$ and observe that $Cle 1$ absolutely won't get the job done, so we can assume $C>1,$ meaning $C-1>0.$ Thus, we get the equivalent inequality $$nge100cdotfrac2C-1C-1=100cdotleft(frac2C-2C-1+frac1C-1right)=200+frac100C-1$$ Does that get you there?

share|cite|improve this answer

edited Mar 16 at 23:04

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161

$endgroup$

add a comment | 

0

$begingroup$

Well, the first thing I notice as I look at this situation is that $f(n)$ and $g(n)$ are negative initially. We're going to want them to be positive, at least, for otherwise, $Ccdot g(n)<f(n)$ for any positive $C.$ Thus, we only need to consider $n>200.$

Now, in the comments, you pointed out that you'd gotten from $$n-100le Ccdot(n-200)$$ to the statement $$ncdot(C-1)-100(C-2)ge 0.$$ Unfortunately, something appears to have gone wrong. Let me take you through the steps. $$n-100le Ccdot(n-200)\n-100le Cn-200C\-100le Cn-n-200C\-100le ncdot(C-1)-200 C\0le ncdot(C-1)+100-200 C\0le ncdot(C-1)+100(1-2C).$$

At this point, you're basically there! Let's rewrite it instead as $$ncdot(C-1)ge100cdot(2C-1),$$ and observe that $Cle 1$ absolutely won't get the job done, so we can assume $C>1,$ meaning $C-1>0.$ Thus, we get the equivalent inequality $$nge100cdotfrac2C-1C-1=100cdotleft(frac2C-2C-1+frac1C-1right)=200+frac100C-1$$ Does that get you there?

share|cite|improve this answer

edited Mar 16 at 23:04

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161

$endgroup$

add a comment | 

0

$begingroup$

Well, the first thing I notice as I look at this situation is that $f(n)$ and $g(n)$ are negative initially. We're going to want them to be positive, at least, for otherwise, $Ccdot g(n)<f(n)$ for any positive $C.$ Thus, we only need to consider $n>200.$

Now, in the comments, you pointed out that you'd gotten from $$n-100le Ccdot(n-200)$$ to the statement $$ncdot(C-1)-100(C-2)ge 0.$$ Unfortunately, something appears to have gone wrong. Let me take you through the steps. $$n-100le Ccdot(n-200)\n-100le Cn-200C\-100le Cn-n-200C\-100le ncdot(C-1)-200 C\0le ncdot(C-1)+100-200 C\0le ncdot(C-1)+100(1-2C).$$

At this point, you're basically there! Let's rewrite it instead as $$ncdot(C-1)ge100cdot(2C-1),$$ and observe that $Cle 1$ absolutely won't get the job done, so we can assume $C>1,$ meaning $C-1>0.$ Thus, we get the equivalent inequality $$nge100cdotfrac2C-1C-1=100cdotleft(frac2C-2C-1+frac1C-1right)=200+frac100C-1$$ Does that get you there?

share|cite|improve this answer

edited Mar 16 at 23:04

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161

$endgroup$

add a comment | 

$begingroup$

Well, the first thing I notice as I look at this situation is that $f(n)$ and $g(n)$ are negative initially. We're going to want them to be positive, at least, for otherwise, $Ccdot g(n)<f(n)$ for any positive $C.$ Thus, we only need to consider $n>200.$

Now, in the comments, you pointed out that you'd gotten from $$n-100le Ccdot(n-200)$$ to the statement $$ncdot(C-1)-100(C-2)ge 0.$$ Unfortunately, something appears to have gone wrong. Let me take you through the steps. $$n-100le Ccdot(n-200)\n-100le Cn-200C\-100le Cn-n-200C\-100le ncdot(C-1)-200 C\0le ncdot(C-1)+100-200 C\0le ncdot(C-1)+100(1-2C).$$

At this point, you're basically there! Let's rewrite it instead as $$ncdot(C-1)ge100cdot(2C-1),$$ and observe that $Cle 1$ absolutely won't get the job done, so we can assume $C>1,$ meaning $C-1>0.$ Thus, we get the equivalent inequality $$nge100cdotfrac2C-1C-1=100cdotleft(frac2C-2C-1+frac1C-1right)=200+frac100C-1$$ Does that get you there?

share|cite|improve this answer

edited Mar 16 at 23:04

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161

$endgroup$

share|cite|improve this answer

edited Mar 16 at 23:04

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161

answered Mar 16 at 22:47

Cameron BuieCameron Buie

86.2k772161