- 07/12/2019 at 10:04 pm #1427769EduGorillaKeymasterSelect Question Language :
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 Ɵ(n2) time. He needs to determine how many sub-problems his algorithm has to create in order to beat Strassen’s algorithm. If his algorithm creates ‘a’ sub-problems, then the recurrence for the running time T(n) becomes T(n) = aT(n/4) + Ɵ(n2) . What is the largest integer value of ‘a’ for which Professor Caesar’s algorithm would be asymptotically faster than Strassen’s algorithm ___________________.
- IIT-JEE, NEET, CAT
- Bank PO, SSC, Railways
- Study Abroad