Computational Tractability

2.1: Computational Tractability

• Proposed Definition of Efficiency:

  1. An algorithm is efficient if it performs well on real input instances.
  2. An algorithm is efficient if it performs quantitatively better than brute-force search in worst-case scenarios.
  3. An algorithm is efficient if it runs in polynomial time.

• A brute-force search is a straightforward but typically inefficient approach involving the examination of all possible solutions