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
The Ntds. dit file is a database that stores Active Directory data, including information about user objects, groups, and group
vladimir2022 [97]

Answer:

I hate it

Explanation:

Mark it as the brainliest if u love god

8 0
2 years ago
If you create and invoke a recursive function without accounting for a base case, what can go wrong?
oksian1 [2.3K]

Every recursive function should have an exit criterion (=handling the base case) to exit the recursion.

Without it, it wil recurse forever, until system resources run out (typically the call stack will overflow and your program will crash).

6 0
3 years ago
Brook is designing a database that customers can use to find their ideal vacation spot. If they only want to see beach vacations
Aleksandr [31]

Answer:

filter the data

Explanation:

its like when you filter a search on y o u t u b e and say u search among us u can filter and say live vids or channel's

7 0
3 years ago
Read 2 more answers
Which attributes are indicators that a website is reliable? Check all that apply is up to date explains sources of data is an ed
Ahat [919]

Answer:

1 - Is up to date

2 - explains sources of data

3 - is an educational website

6 - will not share personal information

7 - has articles written by experts

7 0
2 years ago
A recursive method without a special terminating case would _________. Hint: Self Check 13.3 had infinite number of isLucky() me
asambeis [7]

Answer:

You need exit condition like If, otherwise method will repeat endlessly.

7 0
3 years ago
Other questions:
  • Clicking on the Spelling & Grammar button is one way to correct a spelling error in Word. Please select the best answer from
    7·2 answers
  • When a user inserts a PivotTable, where will it be inserted?
    15·1 answer
  • Why is the most important factor for investors always the quality of the venture's leadership team
    12·1 answer
  • 7.
    15·1 answer
  • Determining the Services Running on a Network Alexander Rocco Corporation has multiple OSs running in its many branch offices. B
    10·1 answer
  • Given main() and a base Book class, define a derived class called Encyclopedia. Within the derived Encyclopedia class, define a
    15·1 answer
  • Which of the following is input devices? (a)Scanner (b) Keyboard (c) Both a and b (d) Plotter​
    5·1 answer
  • Which image file format is the best format to use for photographs on the Web
    15·1 answer
  • Read the citation example, and then use the drop-down menus to identify each part.
    8·2 answers
  • A laptop can be kept on palm to work. [true/false) ​
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!