matrices. Note that we have: There is an alternative way of computing Fibonacci numbers involving Fn (A)-( )(*) Fn+1 If we write the latter equation recursively, we can get Fn Fn (+) = ( })" (F). Let x = ( }) . Fn+1, F1 (a) Show that two 2 2 matrices can be multiplied using 4 additions and 8 multiplications. (b) Show that for all i < n, all entries of Xi have O(n) bits. (Hint: Consider the effect of each matrix multiplication on the bit count). (c) The following recursive algorithm can be used to efficiently compute X". Show that the running time of this algorithm is O(M(n) logn), where M(n) is the time it takes to multiply two n-bit numbers. (Hint: first show that there are O(logn) recursive calls, and then show each call takes at most O(M(n)), you may use the results of parts (a) and (b) to show the latter). Activate Windows