(c) For each of the following function pairs, mark the one with faster asymptotic grows. (i) f(n)= n and g(n) = n [1 mark] (ii) f(n) = 1000 1000 + 1002" and g(n) = 0.00001n! [1 mark] (iii) f(n)= log n+1 and g(n) = 30 (iv) f(n)= 4n and g(n) = 8 log n (v) f(n) (log, n) (log, n) and g(n) = n log n = [1 mark] [1 mark] [1 mark] (d) (i) Provide a (low-level) Turing machine over input alphabet = {a,b} with runtime f(n) = 4 steps for all words which start with a and f(n) = 1 steps else. [2 marks] (ii) Provide a high-level Turing machine with worst-case runtime of O(n!) (and not lower than O(n!)) and best-case runtime of O(n) (and not lower than O(n)). [3 marks]