MadeEasy Test Series: Algorithms - Time Complexity

Question

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 ______-

Comments

4 ??

---

The answer given was 48.But if i substitute 48 in the recurrence relation that it will be more than thetha(n^2),where as question says that it will be thetha(n^2) combining divede and conquer

---

This problem in the CLRS textbook .

Refer once @rahul

Answer 1

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.

Comments

As  mentioned in question that divide and conquer will take total of thetha(n^2),but if we substiture p anything greater than 16 (say 48),then by master theorem it will become n^(log48base4) which is more than n^2,so we will get total complexity more than thetha(n^2).please let me know where i am wrong

---

if u take p=16 it is O(n^2).and it is faster than strassens multiplication.

but here comparision with strassens multiplication.

from p=16 is minimum value and p=48 is max value.

if p>48 then strassens multiplication and Arjuns multiplication runs same speed.(no improvement)

consider large value of P.

---

But the second statement which says that the divide and conquer time is n^2,what is its significance?

I guess divide and conquer time means the complete time execution time.For P more than 16 it will be more than n^2 .Are these statements contradicting or Am i getting them wrong?

---

for more than 16 it will be more than $n^{2}$ and it is faster than starssens multiplication.

p value upto 48,it is better TC.

u compare with strassens multiplication.