# Big theta questionWatch

Announcements
#1
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
#2
bump.
0
5 years ago
#3
(Original post by 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?
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?
0
#4
(Original post by 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?
I don't . Could you explain it a bit more please. Thank you.

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
5 years ago
#5
(Original post by maths learner)
I don't . Could you explain it a bit more please. Thank you.
The statement that is is precisely the statement that there are constants such that for sufficiently large .
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:

Spoiler:
Show
The following lines are equivalent.

Intentionally there is only one line; you're meant to fill in the equivalent following lines.
0
5 years ago
#6
(Original post by maths learner)
I'm completely new to this.
Should have said

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?
0
#7
(Original post by Smaug123)
Should have said

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?
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?
0
#8
(Original post by Smaug123)
Should have said

Suppose is . Then there exist constants such that for sufficiently large. Can you then discover what actually are?
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...
0
5 years ago
#9
(Original post by 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?
Yes on both counts - sorry

(Original post by 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...
; 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
#10
(Original post by 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?
Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1
0
5 years ago
#11
(Original post by maths learner)
Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1
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".
0
#12
(Original post by 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".
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?
0
5 years ago
#13
(Original post by 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?
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
#14
(Original post by 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".
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.
0
5 years ago
#15
(Original post by maths learner)
Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1
(Original post by 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.
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
#16
(Original post by 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.
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.
0
5 years ago
#17
(Original post by 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.
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.
1
#18
(Original post by 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.
Thank so much for all the help. Legend.
0
5 years ago
#19
(Original post by maths learner)
Thank so much for all the help. Legend.
No problem
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Bournemouth University
Wed, 19 Feb '20
• Buckinghamshire New University
Wed, 19 Feb '20
• University of Warwick
Thu, 20 Feb '20

### Poll

Join the discussion

Yes (15)
28.3%
No (28)
52.83%
Don't know (10)
18.87%