In the RAM model we assume that multiplication of two n-bit numbers takes constant time however this is not actually the case. One approach to multiplying two large numbers is to break them up by powers of the base, for example (in base 10 ) 913302=(9102+1101+3100)(3102+2100)=27104+3103+9102+18102+2101+6100=275726. This works nicely as multiplying by a power of the base (i.e. 104 above or 23 if we are working in binary) is quick, since you just shift the digits. This suggests a way of breaking the problem down into smaller sub-problems. Generally, given two n-bit numbers n1 and n2 we express n1=a12n/2+b1 and n2=a22n/2+b2 and then (ignoring shifting by powers of 2 and some additions) we have broken the problem of multiplying two n-bit numbers into the 4 multiplications of n/2-bit numbers. This approach leads to an O(n2) algorithm. However, there is a smarter trick. Given n1=a12n/2+b1 and n1=a22n/2+b2 we let c=a1a2,d=b1b2ande=(a1+a2)(b1+b2)cd, Then we have the expression n1n2=c2n+e2n/2+d Notice here that we used only 3 multiplications of n/2-bit numbers, we used more additions but these are 'cheap' - we can assume that adding two n-bit numbers can be done in time O(n). Likewise assume multiplication by any power 2k takes time O(k). (i) Develop this idea (the equations given by (1) and (2)) into an algorithm for multiplying two n-bit numbers and provide pseudocode, explaining clearly which algorithmic principles you are using. [8 marks] (ii) Show correctness of your algorithm. This requires verifying the formula given by (2) holds and arguing that your algorithm computes this correctly. [8 marks] (iii) Analyse your pseudocode to derive a recurrence relation for T(n), the running time of your algorithm on an input of two numbers both with n bits. [7 marks] (iv) Solve this relation to give the asymptotic running time of your algorithm. You can either prove this running time by induction or use the Master theorem, however in the case of the Master theorem you need to justify why your application is valid. [7 marks]