3.17 Algorithmic Efficiency

Problem Definition A general description of a task that may be solved algorithmically

Decision Problem Definition A problem with a yes or no answer

Efficiency Definition Amount of computational resources used by an algorithm

Efficiency is often determined by counting the number of operations an algorithm performs.

An algorithm's efficiency is often described by a function \(f(n)\) that outputs the number of operations for \(n\) amount of arguments. An algorithm with polynomial efficiency is described by a polynomial function (e.g. \(f(n)=n^2\)). Same goes for other efficiencies like exponential or factorial.

Algorithms with polynomial efficiency or lower are run in reasonable time. Algorithms with exponential or factorial efficiencies or higher are run in unreasonable time.

Different algorithms solving the same problem can have different efficiencies as some may have more operations.

Heuristic Definition A technique used to solve a problem that may not be completely accurate when 100% accurate solutions are impractical

Practice problems can be found in this, this, and this Khan Academy link.

Go Back