The problem that i want to ask is 4.5-2

1.0 TIUJ UJ the master theorem 4.5-2 Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen's algorithm. His algorithm will use the divide- and-conquer method, dividing each matrix into pieces of size n/4 x n/4, and the divide and combine steps together will take (na) time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen's algo- rithm. If his algorithm creates a subproblems, then the recurrence for the running time T(n) becomes T(n) = aT(n/4) + O(n). What is the largest integer value of a for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm? Use the master method to show that the solution to the binary-search recurrence T(n) = T(n/2) + (1) is T(n) = O(Ign). (See Exercise 2.3-5 for a description of binary search.) 4.5-4 Can the master method be applied to the recurrence T(n) = 47(n/2) + n2 lg n? Why or why not? Give an asymptotic upper bound for this recurrence. fm) for some constant c