AP CPS - Algorithmic Complexity

An algorithm that needs n steps is __

• linear

• polynomial

• exponential

• factorial

An algorithm that needs n^4 steps is __

• linear

• polynomial

• exponential

• factorial

An algorithm that needs n*10+5 steps is __

• linear

• polynomial

• exponential

• factorial

An algorithm that needs 3^n steps is __

• linear

• polynomial

• exponential

• factorial

which time complexities are reasonable

• linear

• logarithmic

• exponential

• polynomial

• factorial

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?

• Adding an item to a list of n elements, which can be done in constant time.

• Planning an optimal delivery route that visits each of n locations exactly once, which can require exploring n! possible paths.

• Performing a binary search on a sorted list of n items, which requires at most log n comparisons.

• Performing a binary search on a sorted list of n items, which requires at most \log n comparisons.

• 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^2 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 2^n steps to draw n shapes.

• A

• B

• C

• D

Match the following

• Constant

• Time Complexity of adding a number to a list

• Linear

• Time Complexity of Linear Search

• Factorial

• Time Complexity of Travelling Salesman

• Logarithmic

• Time Complexity of Binary Search