edited by
661 views
0 votes
0 votes
Professor Arjun develops an algorithm to multiply two square matrix that is asmptoticaly faster than strassen's algorithm using divide and conquer method . Arjun's algorithm divide matrix into pieces of $\frac{n}{4} \times \frac{n}{4}$ create $'P'$ subproblems and divide and conquer method together will take $\Theta (n^{2})$ time The recurrence for running time beomes :
$T(n)= P T(\frac{n}{4})+\Theta (n^{2})$

Then the largest value of $P$ is ______-
edited by

1 Answer

Best answer
5 votes
5 votes

Arjun's matrix multiplication runs faster than Strassens matrix multiplication.

Strassens matrix multiplication is=$n^{\log_{2}^{7}}$.

Arjuns matrix multiplication time complexity=

T(n)=p*T(n/4)+$\theta (n^{2})$

Apply master's theorem TC=$n^{\log_{4}^{p}}$.

In the problem Arjuns TC is less than Strassens multiplication.

$n^{\log_{2}^{7}} >n^{\log_{4}^{p}}$

$n^{\log_{2}^{7}} >n^{\log_{2}^{p^{1/2}}}$

7 >$p^{1/2}$

49>p.

so P value is less than 49 it is equall to 48.

selected by

Related questions

1 votes
1 votes
1 answer
1
Markzuck asked Jan 6, 2019
491 views
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
0 votes
0 votes
1 answer
2
Markzuck asked Dec 29, 2018
775 views
cant we write the recurrance relation for bar() as T(n) = 5T(n-1) + c,like cant we take both the recurrance call as combined as both have same parameter?and if not, then ...
1 votes
1 votes
0 answers
3
1 votes
1 votes
1 answer
4