Math Is Fun Forum

harrorm

Member

Registered: 2016-06-27

Posts: 8

Need help understanding this proof

Problem: Show that f(n) = 1/2n^2 - 1/2n = theta(n^2)

theta(g(n) = { f(n) : there exist positive constants c1, c2, and n0 such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n >= n0

Proof:
1. 1/2n^2 - 1/2n <= 1/2n^2 ----> for all n >= 0 c2 = 1/2 ------ for this does c2 = 1/2 because it can be any positive constant?
2. 1/2n^2 - 1/2n >= [1/2n^2 - 1/2n * 1/2n] -----> for all n >= 2 -------- everything in the bracket, I don't understand where it came from

So for #2, where did the "1/2n^2 - 1/2n * 1/2n" come from? I know it suppose to represent c1g(n), but not sure why it's 1/2n^2 - 1/2n * 1/2n and not 1/2n^2 like for c2g(n)

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Need help understanding this proof

Otherwise you would have put 1/(2n)^2-1/(2n)

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

thickhead

Member

Registered: 2016-04-16

Posts: 1,086

Re: Need help understanding this proof

---

{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}