Strassen Multiplication Count

Problem

Return the number of scalar multiplications used by the Strassen recurrence on a power-of-two matrix size n.

The recurrence is T(1) = 1 and T(n) = 7 * T(n / 2), so the count is 7 ** log2(n). Return 0 for a non-positive or non-power-of-two input.

Hint

Seven recursive block products replace the eight of the naive divide and conquer.

case 1

in: [1]

expected: 1

case 2

in: [2]

expected: 7

case 3

in: [4]

expected: 49

case 4

in: [8]

expected: 343

case 5

in: [0]

expected: 0

Starter codePython

def strassen_multiplications(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor