$[$Marks $15]$

Mark the most precise classification applicable to each of the following pairs of

functions. Tick $($A$)$ if $f(n)=O(g(n)),$ but $f(n)(g(n))$; $($B$)$ if $f(n)=(g(n)),$

but that $f(n)O(g(n))$; and $(C)$ if $f(n)=(g(n)).$

$[$Marks $15]$

Suppose that the running time of algorithm $A$ is given by the recurrence

$T(n)=6T(\frac{n}{2})+n^2.$ While a competing algorithm $B$ has a running time of

$S(n)=aS(\frac{n}{3})+n^2.$ What is the largest value for a such that $B$ is

asymptotically faster than $A.$ Show all your calculations.