Register

Test by Bikram | Algorithms | Test 2 | Question: 10

• edited by
384 views
1 votes
1 votes

In Strassen's Matrix Multiplication, what is the number of additions and multiplications done to get a better complexity than the normal matrix multiplication?

  1. $7$ and $16$
  2. $18$ and $7$
  3. $10$ and $8$
  4. $7$ and $7$
• edited by
User Avatar

2 Answers

Best answer
2 votes
2 votes

Using Divide and Conquer normal matrix multiplication would take : T(n)= 8T(n/2) + 4(n/2)2          

therefore time complexity will be O(n3)

with Strassens algorithm time taken is T(n)= 7T(n/2) + 18(n/2)2

therefore time complexity will be O(n2.81)

• selected by
User Avatar
0 votes
0 votes
intituive from the stratssen's equation.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Bikram asked May 26, 2017
486 views
Test by Bikram | Algorithms | Test 2 | Question: 30
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15, q(2)= 0.1, q(3) = 0.05$ is: $1.65$ $1.95$ $1.8$ $2.1$
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
User Avatar
2 votes
2 votes
2 answers
3
Bikram asked May 26, 2017
368 views
Test by Bikram | Algorithms | Test 2 | Question: 28
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest paths from node G are _________.
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
User Avatar
1 votes
1 votes
2 answers
4
Bikram asked May 26, 2017
486 views
Test by Bikram | Algorithms | Test 2 | Question: 27
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
User Avatar
Link Copied!