Part B [3] Suppose a sorting algorithm performs f(n) = 6n2 + 3n + 1 comparisons on input size n, and it treats an input of size q in 1 minute. What is the maximum input size the algorithm can treat in t minutes (for t > 2). Hint 1: consider q as a given constant (that is, your answer will look like f(t) =). Hint 2: you may find it easier to proceed by first defining another function which maps instance size to time, where time is defined in terms of q. Find an answer to the same question for another algorithm that performs g(n) = 21n2 + In + 2 comparisons. What can you tell about the growth of maximum input size with respect to the allowed computational time for these two algorithms? That is, for both of these algorithms find functions that take an allowed computational time and return the maximum problem size. [4] (i) Prove that f(n) = 5n2-1 +42 is O(na) by finding constants c and no such that f(n) no. (ii) Prove that f(n) = 3n2 +12n +16 is 12(na) by finding constants c and no such that f(n) > cn2 whenever n >no