Algorithm Efficiency

For which of the following situations would it be best to use a heuristic in order to find a solution that runs in a reasonable amount of time?

• Appending a value to a list of n

  elements, which requires no list elements be examined.

• Finding the fastest route that visits every location among n

  locations, which requires n!

  possible routes be examined.

• Performing a binary search for a score in a sorted list of n

  scores, which requires that fewer than n

  scores be examined.

• Performing a linear search for a name in an unsorted database of n

  people, which requires that up to n

  entries be examined.

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.

Based on the values in the table, which of the following best characterizes the algorithm for drawing n

shapes, where n

is a very large number?

• The algorithm runs in a reasonable amount of time because it will use approximately n

  steps to draw n

  shapes.

• The algorithm runs in a reasonable amount of time because it will use approximately N ² steps to draw n shapes.

• The algorithm runs in an unreasonable amount of time because it will use approximately n steps to draw n shapes.

• The algorithm runs in an unreasonable amount of time because it will use approximately N ² steps to draw n shapes.

• Algorithm A

• Algorithm B

• Algorithm C

• Algorithm D