Theta Analysis Clarifications

The purpose of this document is to clarify some issues about theta notation. Lets say we are trying to prove the following:
The function 3n^2+3n is THETA(n^2)
To prove this we need to prove that there exist positive constants c1, c2, and n0 such that the following is true for all n >= n0:
c1*g(n) <= f(n) <= c2*g(n)
for some n.
where g(n) is the same function for the upper bounds and the lower bounds. In this case, g(n) = n^2. The big choice here is to determine the values of the constants that make this true, i.e. for what n is this valid and what c1 and c2 values make good bounds. c1 and c2 are just the coefficients to the functions we choose. They must be positive, and that is really the only restriction to them. So lets get on with this great proof!

I will guess that n0 = 1 will work, so we know n >= 1. Now we need to try to determine a lower bound for the f(n) function. I'm going to guess a function and coefficient for the lowerbound, and see if it works. Lets try 

3n^2
So my c1 value is 3 for this guess. The proof goes as follows: 
n >= 1 >= 0       (assumption from above)
3n >= 0           (multiplying both sides by 3)
3n^2+3n >= 3n^2   (adding equals to both sides (3n^2)).
So now we have proven that 3n^2 is a good lower bound for f(n). So now we need to determine an upper bound, again we will make a guess, and see if it works. I will choose: 
4n^2
Why would I choose this? I guess that 4n^2 will eventually always be larger than 3n^2 + 3n. When will this be true? If I subtract 3n^2 from both of these, I get the equation: 
3n <= n^2
When will this be true? It'll be true when n >= 3! Therefore, we now need to take n0 = 3, and c2 = 4. and the proof follows: 
n >=3             (assumption)
n^2 >= 3n         (multiplying by equals (n))
4n^2 >= 3n^2 + 3n (adding equals (3n^2))
The above is true for all n >= 3. If we now combine both of the above proofs, we can see that n0 must be 3, since this will work for both proofs. Recall in the first case above, n had to be greater than or equal to zero, so for both inequalities to be true, n must be greater than or equal to 3. So our final answer is: 
3n^2 + 3n is THETA(n^2)  for c1 = 3, c2 = 4, n0 = 3, i.e. true for all n >= 3

Last modified: Thu Oct 12 09:58:21 EDT 2000