Expert: Paul Klarreich - 12/7/2011

Question
a.Program speed, or runtime, is an important concept in computer programming, and it is measured in terms of the number of mathematical operations made during one run of the program. For example, the expression x3 – 2x + 3 has five operations. If we write it as x*x*x – 2*x + 3, we see that there are three multiplications, one addition, and one subtraction.
◦If you had to compute the polynomial (x + 3)(x – 3) for a certain value of x (the actual value of x does not matter), how many mathematical operations (addition, subtraction, multiplication, or division) would be made? (Count the number of each type of operation you see in the expression.)
◦Now, multiply the original (x + 3)(x – 3) polynomial (FOIL). In the new version of the expression (polynomial), how many operations are there?
b.The time it takes to multiply two matrices of size n is determined by the polynomial expression 2n3 – n2. For example, it takes 45 operations to multiply two 3x3 matrices. Compute the number of operations required to run a program that multiplies two matrices of size 20.

Answer
Questioner: Patti
Country: Texas, United States
Category: Calculus
Private: No
Subject: How Do You Multiply Matrices?
Question: a.Program speed, or runtime, is an important concept in computer programming, and it is measured in terms of the number of mathematical operations made during one run of the program. For example, the expression x3 – 2x + 3 has five operations. If we write it as x*x*x – 2*x + 3, we see that there are three multiplications, one addition, and one subtraction.
◦If you had to compute the polynomial (x + 3)(x – 3) for a certain value of x (the actual value of x does not matter), how many mathematical operations (addition, subtraction, multiplication, or division) would be made? (Count the number of each type of operation you see in the expression.)
◦Now, multiply the original (x + 3)(x – 3) polynomial (FOIL). In the new version of the expression (polynomial), how many operations are there?

>>> You certainly don't need me for this.

b.The time it takes to multiply two matrices of size n is determined by the polynomial expression 2n3 – n2. For example, it takes 45 operations to multiply two 3x3 matrices. Compute the number of operations required to run a program that multiplies two matrices of size 20.


If you write  f(n) = 2n^3 - n^2,  you see that:

f(3) =  2(3)^3 - (3)^2 = 45

So compute

f(20) = 2(20)^3 - (20)^2


That's all.