# Big theta question Watch

Announcements

Page 1 of 1

Go to first unread

Skip to page:

Report

#3

(Original post by

Hi,

I'm trying to show that is big theta(n^2). Is it as simple as this:

Then as n tends to infinity the n squared factor increases much faster, so it's big theta n squared for some constants K1 and K2?

**maths learner**)Hi,

I'm trying to show that is big theta(n^2). Is it as simple as this:

Then as n tends to infinity the n squared factor increases much faster, so it's big theta n squared for some constants K1 and K2?

0

reply

(Original post by

That's not really a proof. You've shown that if there are such that then it is big theta(1). You're actually aiming for - do you see why?

**Smaug123**)That's not really a proof. You've shown that if there are such that then it is big theta(1). You're actually aiming for - do you see why?

Oh is it because I want to show its big theta(n^2) so since the K1 and K2 are just constants, then multiplying them by n^2 gives a proportionality factor... I know what I mean but not sure how to word it aha. Or for that matter how to actually prove this is big theta(n^2). I'm completely new to this.

0

reply

Report

#5

(Original post by

I don't . Could you explain it a bit more please. Thank you.

**maths learner**)I don't . Could you explain it a bit more please. Thank you.

You have apparently shown that there are constants such that . (This is false, by the way, and it's false because your first line is false.)

Essentially, you started from a false premise, and derived a conclusion which is both false and unrelated to the problem at hand.

The appropriate starting line is:

Intentionally there is only one line; you're meant to fill in the equivalent following lines.

0

reply

Report

#6

(Original post by

I'm completely new to this.

**maths learner**)I'm completely new to this.

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?

0

reply

(Original post by

Should have said

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?

**Smaug123**)Should have said

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?

Do c and C have to be positive?

0

reply

**Smaug123**)

Should have said

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?

0

reply

Report

#9

(Original post by

I'll have an attempt. Not too sure how to go about it though, also are you missing a -1 in between the inequalities?

Do c and C have to be positive?

**maths learner**)I'll have an attempt. Not too sure how to go about it though, also are you missing a -1 in between the inequalities?

Do c and C have to be positive?

(Original post by

is it 1/2 ?. I re arranged each inequality for c and then did the limit as n tends to infinity so took the ratio of the n^2...

**maths learner**)is it 1/2 ?. I re arranged each inequality for c and then did the limit as n tends to infinity so took the ratio of the n^2...

For the upper bound: notice that both c and C can't be the same thing - otherwise you're asserting that is precisely for sufficiently large n, and that's false. You're going to need C to be bigger. Have a guess? Can you show your guess works?

0

reply

(Original post by

Yes on both counts - sorry

; gives for the lower inequality, which is true as long as n is sufficiently large (bigger than 1). So yes, c=1/2 will do. (Note that the constant is not unique - 1/4 would also do. 1/2 is the best bound there is here.)

For the upper bound: notice that both c and C can't be the same thing - otherwise you're asserting that is precisely for sufficiently large n, and that's false. You're going to need C to be bigger. Have a guess? Can you show your guess works?

**Smaug123**)Yes on both counts - sorry

; gives for the lower inequality, which is true as long as n is sufficiently large (bigger than 1). So yes, c=1/2 will do. (Note that the constant is not unique - 1/4 would also do. 1/2 is the best bound there is here.)

For the upper bound: notice that both c and C can't be the same thing - otherwise you're asserting that is precisely for sufficiently large n, and that's false. You're going to need C to be bigger. Have a guess? Can you show your guess works?

0

reply

Report

#11

(Original post by

Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1

**maths learner**)Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1

Now you've found the appropriate c, C. Mathematical pedantry: the proof started out "suppose that the function is ". That is, we assumed what we wanted to prove. We need to make sure that all the steps are iff rather than just implications (although this might be hard because several C, c will do, so some of our steps won't be "only if"). Alternatively, we could re-write the proof, starting out from "let c=1/2, C = 1".

0

reply

(Original post by

Yep, exactly. (Indeed, *any* C will do, as long as it's strictly bigger than 1/2.)

Now you've found the appropriate c, C. Mathematical pedantry: the proof started out "suppose that the function is ". That is, we assumed what we wanted to prove. We need to make sure that all the steps are iff rather than just implications (although this might be hard because several C, c will do, so some of our steps won't be "only if"). Alternatively, we could re-write the proof, starting out from "let c=1/2, C = 1".

**Smaug123**)Yep, exactly. (Indeed, *any* C will do, as long as it's strictly bigger than 1/2.)

Now you've found the appropriate c, C. Mathematical pedantry: the proof started out "suppose that the function is ". That is, we assumed what we wanted to prove. We need to make sure that all the steps are iff rather than just implications (although this might be hard because several C, c will do, so some of our steps won't be "only if"). Alternatively, we could re-write the proof, starting out from "let c=1/2, C = 1".

Proof:

Let from some constants c, C.

This implies that . Then the limit as n tends to infinity is 1/2 therefore c=1/2. Then apply a similar argument for C?

0

reply

Report

#13

(Original post by

Ah okay. Thanks so much. So just to clarify it would go something along the lines of:

Proof:

Let from some constants c, C.

This implies that . Then the limit as n tends to infinity is 1/2 therefore c=1/2. Then apply a similar argument for C?

**maths learner**)Ah okay. Thanks so much. So just to clarify it would go something along the lines of:

Proof:

Let from some constants c, C.

This implies that . Then the limit as n tends to infinity is 1/2 therefore c=1/2. Then apply a similar argument for C?

In this case, any c strictly less than 1/2 will do - that's what you've shown. You could, for instance, say "limit is 1/2, so as n increases, the RHS approaches 1/2 n^2; hence c = 1/4 will do".

0

reply

(Original post by

Strictly speaking you need to show that the limiting process behaves well. For instance, the sequence 1, 2-1/2, 3+1/3, 4-1/4, … is according to your argument, but the function is not with constant c=1 because the terms alternate between below and above n. Constant 1/2 would do there, though.

In this case, any c strictly less than 1/2 will do - that's what you've shown. You could, for instance, say "limit is 1/2, so as n increases, the RHS approaches 1/2 n^2; hence c = 1/4 will do".

**Smaug123**)Strictly speaking you need to show that the limiting process behaves well. For instance, the sequence 1, 2-1/2, 3+1/3, 4-1/4, … is according to your argument, but the function is not with constant c=1 because the terms alternate between below and above n. Constant 1/2 would do there, though.

In this case, any c strictly less than 1/2 will do - that's what you've shown. You could, for instance, say "limit is 1/2, so as n increases, the RHS approaches 1/2 n^2; hence c = 1/4 will do".

0

reply

Report

#15

(Original post by

Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1

**maths learner**)Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1

(Original post by

Hi thanks for all your help . I was just re-reading through and I understand it all apart from one thing. When we assumed C=1, why did we sub the value of 1 in for n... that's the one part I don't get which obviously leads to 0<1 so the inequlity holds.

**maths learner**)Hi thanks for all your help . I was just re-reading through and I understand it all apart from one thing. When we assumed C=1, why did we sub the value of 1 in for n... that's the one part I don't get which obviously leads to 0<1 so the inequlity holds.

What you have done *could* have been a proof - as long as you also show that equality holds with the inequality only for n<0. (You'd do that by solving the quadratic equation .) That would then be like drawing a plot of the function (n against ), and showing that it intersects the n-axis only for n<0; then observing that at n=0 the function lies above the n-axis, so it must also lie above the n-axis for n>0. That turns out to work in this case, because in fact the inequality is always satisfied for all real n, but it's a bit less safe as a method - it might not work so easily in all cases.

0

reply

(Original post by

Ah, I didn't read your answer properly - that line should read (letting C = 1), whence subtracting from both sides will give you an inequality which holds for sufficiently large n.

What you have done *could* have been a proof - as long as you also show that equality holds with the inequality only for n<0. (You'd do that by solving the quadratic equation .) That would then be like drawing a plot of the function (n against ), and showing that it intersects the n-axis only for n<0; then observing that at n=0 the function lies above the n-axis, so it must also lie above the n-axis for n>0. That turns out to work in this case, because in fact the inequality is always satisfied for all real n, but it's a bit less safe as a method - it might not work so easily in all cases.

**Smaug123**)Ah, I didn't read your answer properly - that line should read (letting C = 1), whence subtracting from both sides will give you an inequality which holds for sufficiently large n.

What you have done *could* have been a proof - as long as you also show that equality holds with the inequality only for n<0. (You'd do that by solving the quadratic equation .) That would then be like drawing a plot of the function (n against ), and showing that it intersects the n-axis only for n<0; then observing that at n=0 the function lies above the n-axis, so it must also lie above the n-axis for n>0. That turns out to work in this case, because in fact the inequality is always satisfied for all real n, but it's a bit less safe as a method - it might not work so easily in all cases.

0

reply

Report

#17

(Original post by

Ah okay I get that, but then don't you have to find out what the sufficently large values of n actually are? Otherwise it seems like you're just saying this holds for some large number. :P. Seen as my proof doesn't have to be particularly rigorous I'm happy with just subtracting and using the above though.

**maths learner**)Ah okay I get that, but then don't you have to find out what the sufficently large values of n actually are? Otherwise it seems like you're just saying this holds for some large number. :P. Seen as my proof doesn't have to be particularly rigorous I'm happy with just subtracting and using the above though.

1

reply

(Original post by

Well, you could just say "the values exist, because n^2 gets bigger than n" - that's probably enough for these purposes. To be strictly rigorous, you'd need to find the sufficiently large values, yes.

**Smaug123**)Well, you could just say "the values exist, because n^2 gets bigger than n" - that's probably enough for these purposes. To be strictly rigorous, you'd need to find the sufficiently large values, yes.

0

reply

Report

#19

(Original post by

Thank so much for all the help. Legend.

**maths learner**)Thank so much for all the help. Legend.

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top