79363267

Date: 2025-01-16 23:09:03
Score: 1
Natty:
Report link

Whether b equals 2 or 4 depends on your representation of input size.

If the size of the input is n (i.e., the size of one dimension of each input array), then the running time of the naive algorithm is O(n3) and each square array in each subproblem has dimension n/2. Thus b is 2 and the running time for Strassen's is O(nlog27).

If the size of the input is the number of elements in each array m=n2, then the running time of the naive algorithm is O(m m1/2) = O(m3/2) and each square array in each subproblem has m/4 elements in it. Thus b is 4 and the running time for Strassen's is O(mlog47).

Relative to their representations of input size, these running times are identical since you can map between them by changing the representation with m=n2:

For the naive algorithm, O(n3)=O((m1/2)3) = O(m3/2).

For Strassen's, O(nlog27) = O((m1/2)log27) = O(m(log_2 7)/2)=O(m(log27)/(log24)) = O(mlog47).

Reasons:
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (1):
Posted by: Yaw