1 Algorithm fast mult(A,B,n): pre-: A and B are n-digit natural numbers, wheren is a power of 2 post-: return A B ifn1: else: 4 return A* B 7 assume this takes time proportional to n b - 10m # A-A1+10m+A0 Al-A // b B1-B //b AD A1 -A0 10 #B-B1*10m + B0 12 13 14 15 16 17 term1 - fast_mult(A1, B1, m) term2 - fast_mult(A0, BO, m) term3 - term1 + term2 - fast mult(AD, BD, m) 18 return term1 b2 + term2term3 b Part (a) [4 MARKS] Write a recurrence T(n) to present the number of operations in fast_muft(A, B, n), where n is a power of 2 Briefly explain how your recurrence captures the cost of T(n) 1 Algorithm fast mult(A,B,n): pre-: A and B are n-digit natural numbers, wheren is a power of 2 post-: return A B ifn1: else: 4 return A* B 7 assume this takes time proportional to n b - 10m # A-A1+10m+A0 Al-A // b B1-B //b AD A1 -A0 10 #B-B1*10m + B0 12 13 14 15 16 17 term1 - fast_mult(A1, B1, m) term2 - fast_mult(A0, BO, m) term3 - term1 + term2 - fast mult(AD, BD, m) 18 return term1 b2 + term2term3 b Part (a) [4 MARKS] Write a recurrence T(n) to present the number of operations in fast_muft(A, B, n), where n is a power of 2 Briefly explain how your recurrence captures the cost of T(n)