(10 marks] 1. (a) For each of the following pairs of functions f and g, state which of the five statements f = o(9), f =

[answerhappygod]

10 Marks 1 A For Each Of The Following Pairs Of Functions F And G State Which Of The Five Statements F O 9 F 1 (64.69 KiB) Viewed 72 times

(10 marks] 1. (a) For each of the following pairs of functions f and g, state which of the five statements f = o(9), f = 0(g), f = O(9), f = $2(g), f = w(9) are true. (You may simply list the relevant set of symbols o, 0, 0,12,w). Informally justify your answers. i. f(n) = lg(n"), g(n) =nyn. ii. f(n) = 1g(n!), g(n) = n lgn. (Hint: rewrite lg(n!) as a summation.) (b) A certain algorithm published in 1971 (here called 'A') is able to multiply two n-digit decimal numbers in time (n lg n lg lg n), spectacularly beating the obvious quadratic-time method. In 2019 it was discovered that a more elaborate algorithm ('B') can do the same in time O(n lg n). For the purpose of this question, we shall suppose that multiplying two n-digit numbers using algorithm A always takes between 6n lg ng Ign and 7nlg n lg lg n computation steps, and that doing so with algorithm B always takes between 105n Ign and 120n lg n steps. On the basis of this information, identify: i. A constant N, such that A always performs faster than B on inputs of size <N1. Your N should be as large as possible. ii. A constant N, such that B always performs faster than A on inputs of size > N2. Your N2 should be as small as possible. (You may give your answers as unevaluated expressions.) Explain your reasoning in each case. (c) By developing the idea used in (b), prove that nign o(n lg n lg lgn), arguing rigorously from the formal definition of o. [6 marks) [9 marks)