5. Application: Matrix Multiplicatioin (a) Consider the code below for easy-mult

Question

5. Application: Matrix Multiplicatioin (a) Consider the code below for easy-multiply, which computes the matrix prod- uct of two n × n square matrices of floating-point numbers. Suppose that all primitive operations (*, +,, ) are (1) operations. Provide a tight asymp- totic upper bound on the runtime of easy-multiply in terms of n. (*) Algorithm 1: easy-multiply(A, B) Data: Two n x n, 2-D Arrays A and B of floating point numbers Result: The matrix product AB Result an n × n matrix of zeroes for i - 1 to n do (Note: This operation takes (n2) time) for i-1 to n do for k = 1 to n do Result ili] A i][k] B[k][j] end end end return Result (b) Strassen Matrix Multiplication is an algorithm for matrix multiplication which achieves a runtime asymptotically bounded by 0(n2807) on n × n matrices. De- spite this good runtime bound, this algorithm is slower than easy-multiply on small inputs. Call the routine for Strassen matrix multiplication s-multiply. Consider the following algorithm for matrix multiplication: Algorithm 2: combined-multiply(A, B) Data: Two n × n, 2-D Arrays A and B of floating point numbers Result: The matrix product AB if n 100 then | return easy-multiply(A, B) else |return s-multiply(A, B) end What is the asymptotic runtime of combined-multiply in terms of n? (*) 2

Explanation / Answer

A) We can see that there are three nested for loop , each running for n time

=> So the first for loop will run for n time
=> Second for loop will run for n2 time because first runs for n and second runs n times itself so n*n = n2
=> Third for loop will run for n3 time because second runs for n2 and third runs n times itself so n2*n = n3

So Overall time complexity is O(n3)


B) We can see that the F(n) falls in this way

F(n) = n3 if n < 100

= n2.807 if n > 100

That means if we use the definition of we can see that g(n) for higher value goes below f(n). So we can say that
asymptotic runtime of combined-multiply is ( n2.807 ). We can also write O( n2.807 )

We need to think about larger n and not just 100



Thanks, let me know if there is any concern. PLEASE RATE

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.