question 1:
* When giving a solution of a recurrence, you need to prove the OMEGA, not only the O.
* when proving by induction, the constant in the induction assumption cannot
change at the end of the proof. Here is a (wrong) proof by induction that the solution to
T(n)=2T(n-1)+1 is T(n)=O(n):
We prove by induction that T(n)=O(n). The base case is easy. Let us assume that this is true for n-1.
Then T(n)=2T(n-1)+1=2O(n)+1=O(n). What went wrong here? You should prove by induction that T(n)<=Cn,
where C is some absolute constant. You usually don't bother to specify what C is, but it
should be a constant, which is independent of n.

question 4b:
* many students said something like that their algorithm uses sort and therefore
cannot be better than nlogn. This is of course not a formal argument. Please review
the logic of the reduction, and see how to formally solve this!