q1)
The statement f(n) = Theta(g(n)) => lim_{n->infty} f(n)/g(n) = c is a false statement. For this to be true, we need to prove the limit actually exists! As a counterexample, consider f(n) = n if n is odd else 2n and g(n) = n. There is no limit for this example.
Many people stated f(n) = Theta(g(n)) means that f(n) = cg(n). This is not a true statement. The 2 c's for Theta need not be the same and thus, defining it with 1 c is incorrect.
Stating the definition of f(n) = o(g(n)) as "There exists an n_0 forall c>0 s.t f(n) < cg(n) for n > n_0" is an incorrect statement. It should be "Forall c > 0, there exists an n_0..." The ordering of the statements is critical because in the first case you are stating that for a single n_0, something is true for all c>0. The second case states that forall c>0, there is at least one n_0 that works, but the n_0's need not be the same.
q2)
Many of you did not reference the psuedocode in your proof and thus had indexing errors. Be sure to reference the pseudocode because it may be important.
q3)
There is another master theorem from 211. It is more general and you are welcome to use it. However, there are extra caveats that make it slightly more complex to use, so if you want to use it, make sure you understand those caveats (the importance of the epsilon in the theorem). For an example of how to use our master theorem to solve the extra cases 211's covers, refer to the HW1 solutions question 3d.
q4)
The word "obviously" does not consitute as a proof. If we say prove something, saying "obviously" is not good enough.
To prove an algorithm is just as bad as another asymptotically, you cannot say alg1 = Theta(n^2), alg2 = O(n^2), thus alg2 is as bad as alg1. O(n^2) does not imply that O(n) isn't possible. Additionally, proving O(n^2) also isn't enough. Omega is what is critical here.
When you use linearity of expectation, you should formally define your RVs, IRVs and events. Be formal. Write formal proofs.