Sunday, 15 September 2013

Trouble understanding how to pick constants to prove big theta

Trouble understanding how to pick constants to prove big theta

So I'm reading Introductions to Algorithms and sometimes I wish it would
be a little bit more friendly with how it explains topics. One of these
topics is proving big-theta.
I understand that the definition of BigTheta is as follows:
BigTheta(g(n) = f(n) if there exists positive constants c1, c2, and n0
such that 0 <= c1g(n) <= f(n) <= c2g(n) for all n>= n0.
In other words, for f(n) and g(n), f(n) can be bounded by c2g(n) from
above and bounded below by c1g(n).
So the example in the book goes:
Show that 1/2(n^2) - 3n = BigTheta(n^2)
From the definition of big theta:
c1n^2 <= 1/2(n^2)-3n <= c2n^2
CLRS begins by dividing by the largest order term of n which is n^2 to get
c1 <= 1/2 - 3/n <= c2
From here we split the problem into two parts, the right-hand inequality
and the left-hand inequality.
On the right hand side: CLRS chooses c2 >= 1/2 because for n>1, (1/2 -
3/n) can never be less than 1/2 since 3/n goes to 0 as n goes to infinity.
Now this is where I start to get lost.
On the left hand side: CLRS chooses c1 = 1/14. (Not sure why) and n>=7.
I'm not sure what the significance of these choices is. At n=<6, (1/2-3/n)
becomes negative. But why 1/14 for c2? I'm just not sure how they arrived
at solving the left hand side and the book doesn't really explain it well
for me.

No comments:

Post a Comment