volume_mute

Why would one opt for an approximation algorithm not an exact one?

publish date: 2022/06/09 09:03:00 GMT+10

volume_mute
  1. Some problems cannot be solved exactly
  2. The algorithm to find the exact solution may be unacceptably slow because of the complexity of the problem
  3. It may be a part of a more sophisticated algorithm that solves a problem exactly
True
False

Correct Answer

True

Explanation

That is true.

Regarding the first point, there are some problems that cannot be solved exactly in all its instances.  For example, finding a square root of a number, solving nonlinear equations, and evaluating definite integrals.

Reference

Introduction to the Design and Analysis of Algorithms, 3rd edition

Quizzes you can take where this question appears