1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
NARA [144]
3 years ago
9

Suppose you wish to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. Your algo

rithm will use divide-and-conquer, dividing each matrix into pieces of size n/8 × n/8, and the divide and combine steps together will take Θ(n2) time. You need to determine how many subproblems your algorithm has to create in order to beat Strassen’s algorithm. If your algorithm creates a subproblems, what is the largest integer value of a for which your algorithm would be asymptotically faster than Strassen’s algorithm?
Computers and Technology
1 answer:
Kazeer [188]3 years ago
5 0

Answer:

The number of subproblems are given as T(n)=a*T(n/8)+\theta(n^2) while the value of T(n) to be less than S(n) is for 342.

Explanation:

The number of subproblems are given as

T(n)=a*T(n/8)+\theta(n^2)

Asymptotic running time for Strassen’s algorithm is S(n)=\theta(n^{log(7)})

Now, when a increases, number of subproblems determines the asymptotic running time of the problem and case 1 of master theorem applies. So, in worst case, asymptotic running time of the algorithm will be

T(n)=\theta(n^{logb(a)})=\theta(n^{log8(a)})=\theta(n^{log_{2}(a^{1/3})})

Now, for T(n) to be smaller than S(n)

n^{loga^{1/3}}

So,

log(a^{(1/3)})

So,

a=342

You might be interested in
[c++] Write a recursive function takes a word string as input argument and reverse the word. Print out the results of recursive
Aleks04 [339]
I will try to give you the best answer I can possibly come up with. 
The easy way to get it is to store it into an array of strings and print the array of string backwards. You can do that by starting at the last part of the array down to the first letter.
3 0
2 years ago
The reason for prioritizing your work is to get the
7nadin3 [17]

Answer:

a

Explanation:

3 0
2 years ago
Is a three-prong grounding plug with the third pong broken-off safe to use.
ad-work [718]
What is the answer choices dude
8 0
3 years ago
Have you seen this ProFlipperz Review? It is a course on how to flip every day household items for a profit.
Nadusha1986 [10]

Well if you have one I know it's cool but don't flip it all the time

Explanation:

6 0
2 years ago
All of the following are computer hardware servicing tools EXCEPT​
andrey2020 [161]

Answer:

Shovel

Explanation:

7 0
2 years ago
Other questions:
  • Ana works in the medical records department at a large medical office. Her job includes scanning and uploading medical records i
    15·1 answer
  • A(n) ____ is an attack that takes advantage of a system vulnerability.
    7·1 answer
  • 50 POINTS!!!!
    8·1 answer
  • __ are designed to be used with everyday objects, such as home appliances, gaming consoles, digital cameras, e-readers, digital
    13·1 answer
  • _______ is a form of crime that targets a computer system to acquire information stored on that computer system, to control the
    12·1 answer
  • A palindrome is a string that is the same regardless of whether your read it forward or backward, assuming you ignore the spaces
    14·1 answer
  • How many times would the following loop iterate?
    15·1 answer
  • A form letter can be customized by using different fields in a __________.
    15·2 answers
  • What would give Lucy, an entry-level candidate, an edge over others while she seeks a programmer’s position? Lucy, an entry-leve
    11·1 answer
  • Digital Sep <br> helps as reimagine outcomes true or false
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!