roject Activity $8\mathrm{.}4.$ We introduce a little notation to help us describe the efficiency of our cal$-$

culations. We won$$t be formal with this notation, rather work with it in an informal way. Big O

$($the letter $$O$)$ notation is used to describe the complexity of an algorithm. Generally speaking,

in computer science big O notation can be used to describe the run time of an algorithm, the space

used by the algorithm, or the number of computations required. The letter $$O$$ is used because the

behavior described is also called the order. Big O measures the asymptotic time of an algorithm, not

its exact time. For example, if it takes $6$n$2$ n $+8$ steps to complete an algorithm, then we say that

the algorithm grows at the order of n$2($we ignore the constants and the smaller power terms, since

they become insignificant as n increases$)$ and we describe its growth as O$($n$2).$ To measure the

efficiency of an algorithm to determine a matrix product, we will measure the number of operations

it takes to calculate the product.

$($a$)$ Suppose A and B are n $$ n matrices. Explain why the operation of addition $($that is$,$

calculating A $+$ B$)$ is O$($n$2).$

$($b$)$ Suppose A and B are n $$ n matrices. How many multiplications are required to calculate

the matrix product AB$?$ Explain.

Section $8.$ Matrix Operations $167$

$($c$)$ The standard algorithm for calculating a matrix product of two n $$ n matrices requires n$3$

multiplications and a number of additions. Since additions are much less costly in terms

of operations, the standard matrix product is O$($n$3).$ We won$$t show it here, but using

Strassen$$s algorithm on a product of $2$m $2$m matrices is O$($nlog$2(7)),$ where n $=2$m$.$

That means that Strassen$$s algorithm applied to an n $$ n matrix $($where n is a power of

$2)$ requires approximately nlog$2(7)$ multiplications. We use this to analyze situations to

determine when Strassen$$s algorithm is computationally more efficient than the standard

algorithm.

i$.$ Suppose A and B are $55$ matrices. Determine the number of multiplications re$-$

quired to calculate the matrix product AB using the standard matrix product. Then

determine the approximate number of multiplications required to calculate the matrix

product AB using Strassen$$s algorithm. Which is more efficient? $($Remember$,$ we

can only apply Strassen$$s algorithm to square matrices whose sizes are powers of $2.)$

ii$.$ Repeat part i$.$ with $125125$ matrices. Which method is more efficient?