Question

A graphic artist uses a program to draw geometric shapes in a given pattern. The program uses an algorithm that draws the shapes based on input from the artist. The table shows the approximate number of steps the algorithm takes to draw different numbers of shapes. Number of Shapes Drawn Number of Steps 4 17 5 24 6 35 7 50 Based on the values in the table, which of the following best characterizes the algorithm for drawing shapes, where is a very large number? The algorithm runs in a reasonable amount of time because it will use approximately steps to draw shapes. Option A,The algorithm runs in a reasonable amount of time because it will use approximately n steps to draw n shapes. A The algorithm runs in a reasonable amount of time because it will use approximately steps to draw shapes. Option B,The algorithm runs in a reasonable amount of time because it will use approximately n squared steps to draw n shapes. B The algorithm runs in an unreasonable amount of time because it will use approximately steps to draw shapes. Option C,The algorithm runs in an unreasonable amount of time because it will use approximately n steps to draw n shapes. C The algorithm runs in an unreasonable amount of time because it will use approximately steps to draw shapes.

Answer 1

Compute successive differences: 24−17=7, 35−24=11, 50−35=15. The second differences are 11−7=4 and 15−11=4 (constant), so the steps follow a quadratic function. Fitting gives S(n)=2n^2−11n+29, so for large n the dominant term is 2n^2. Hence the algorithm is quadratic (Θ(n^2)), so choose option B.