Let x and y be two n bit numbers
Devide x in two n/2 bit no say a,b similarly y in c,d
To get x*y we need to perform bd,ad,bc,ca that is 4 n/2 bit multiplication and some addition and shift operation in o(1) so recurrence relation can be written as
T(n)=4*T(n/2)+o(1)
Solve this using masters theorem
We get T(n)=o(n2)
