Unable to typeset  PDF Format  Error 

Running Time
Task
Many computer applications use very complex mathematical algorithms. The faster the algorithm, the more smoothly the programs run. The running time of an algorithm depends on the total number of steps needed to complete the algorithm. For image processing, the running time of an algorithm increases as the size of the image increases.
For an $n$by$n$ image, algorithm 1 has running time given by $p(n) = n^3+3n+1$ and algorithm 2 has running time given by $q(n)=15n^2+5n+4$ (measured in nanoseconds, or $10^{9}$ seconds ).
 Compute the running time for both algorithms for images of size 10by10 pixels and 100by100 pixels.
 Graph both running time polynomials in an appropriate window (or several windows if necessary).
 Which algorithm is more efficient?
IM Commentary
This task provides an application of polynomials in computing. Anybody who has been on the internet and waited for an image to refresh or a webpage to reload has experience with computer algorithm complexity, even if they may not be aware of the technical term. It makes intuitive sense that larger images take longer to reload than smaller images. That said, instructor may with to give a basic explanation of how computer algorithms work: Algorithms perform very basic steps over and over (such as single digit addition and multiplication often in loops). They require more time if they work with larger objects.
This purpose of this task is to serve as an introduction, and motivation, for the study of end behavior of polynomials, content specifically addresses in standard FIF.C7c. The task might also be used as an introduction to the idea that the leading term of a polynomial dominates the output values for large input values. Instructors wishing to pursue this route might ask students if they can identify what about the algebraic expressions for $p(n)$ and $q(n)$ could have been used to predict which of the algorithms would run faster on large images.
Brief commentary on the three parts of the problem:

Part (a) is very straight forward but gets the point across that polynomials get larger very fast as the input increases.

Part (b) requires the use of a graphing calculator or computer program. It helps to build a very important skill, to play with graphing windows, since the graph will appear very different and show different aspects of the situation depending on the chosen window. This also shows a very important aspect of polynomials  long term vs. short term behavior. This is an opportunity to engage in SMP 5  Use Appropriate Tools Strategically.

Part (c) is a discussion question where students have to support their reasoning.
Solution

For a 10by10 image, the two algorithms take respectively $$ p(10) = 10^3 + 3 (10) + 1 = 1031\quad\quad\text{ and }\quad\quad q(10)=15 (10^2) + 5(10) + 4 = 1554 $$ nanoseconds.
For a 100by100 image, we have $$ p(100) = 100^3+3(100)+1 = 1,\!000,\!301\quad\text{ and }\quad q(100)=15 (100^2) + 5(100) + 4 = 150,\!504 $$ nanoseconds.
It is already interesting to note that Algorithm 1 runs faster on the 10by10 image, whereas Algorithm 2 runs faster on the 100by100 image.

We need several windows to see all the important features of the two graphs. The first graph shows the running times for very small images. In fact, and we can see that initially the running time for algorithm 1 is shorter.
The second window shows the intersection point of the two graphs. Around image sizes $n=15$ algorithm 2 starts to have shorter running times than algorithm 1.
For larger image sizes it is very clear that algorithm 2 has shorter running times than algorithm 1.
 For very small images, algorithm 1 has a shorter running time than algorithm 2. However, for any kind of realistic image size, algorithm 2 has much shorter running times than algorithm 1.
Running Time
Many computer applications use very complex mathematical algorithms. The faster the algorithm, the more smoothly the programs run. The running time of an algorithm depends on the total number of steps needed to complete the algorithm. For image processing, the running time of an algorithm increases as the size of the image increases.
For an $n$by$n$ image, algorithm 1 has running time given by $p(n) = n^3+3n+1$ and algorithm 2 has running time given by $q(n)=15n^2+5n+4$ (measured in nanoseconds, or $10^{9}$ seconds ).
 Compute the running time for both algorithms for images of size 10by10 pixels and 100by100 pixels.
 Graph both running time polynomials in an appropriate window (or several windows if necessary).
 Which algorithm is more efficient?
Comments
Log in to commentElizabeth says:
9 monthsThe PDF for this task cuts off the text on the righthand margin.