1. 

We need to pick c>0 and m such that

n^3 - 1000 n^2 >= c n^3 	for all n > m.

i.e., n - 1000 >= cn 

i.e., n > 1000/(1-c).

The above is true for c = 1/2 and n > 2000.
so, pick c = 1/2 and m = 2000.


2. 
Let A[1...n] be the array storing the a_i's.
For simplicity, assume n is a multiple of two.
Do a binary search. 
Compare A[n/2] with (n/2).

If A[n/2] = n/2, then return TRUE.
If A[n/2] > n/2, then check recursively in A[1..n/2] half of the array.
If A[n/2] < n/2, then check recursively in A[n/2 .. n] half of the array.

3. 

Consider three jobs: (0,10,10), (0,5,7) and (6,10,7).
Greedy picks (0,10,10) with a total profit of 10.
Optimal picks both (0,5,7) and (6,10,7) with a total profit of 14.

4. 

S_i = MAX (S_{i-1}, 	S_j + q_i), where j is the maximum number such that
			s_i > f_j. Here, s_i is the start time of i-th job.

Complexity of above is O(n log n), since there are n values to be computed
and finding "j" for an "i" takes O(log n) binary search.