1. (20 points) Let f(n) and g(n) be asymptotically nonnegative func- tions. Show that max(f(n), g(n)) = (f(n) + g(n)). 2. (20 points) Show that for any real constants a and b with b>0, we have (n + a) = O(n). Divide-and-Conquer 3. (20 points) Use the substitution method to show that the running time of the recurrence is O(n). T(n) = T(n-1) + n