Algorithmic Efficiency

A problem is a general description of a task that can (or cannot) be solved algorithmically.

An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2, 3, 1, 7) is an instance of the problem.

Efficiency is an estimation of the amount of computational resources used by an algorithm.

Efficiency is typically expressed as a function of the size of the input, for example the size of the list. It can be either worst-case complexity or average-case complexity.

An algorithm's efficiency can be informally measured by determining the number of times a statement or group of statements executes.

Different correct algorithms for the same problem can have different efficiencies. For example, a sorting algorithm that requires more computations is slower than a different sorting algorithm that requires less.

In each example below, let efficiency be the number of times a math operation statement is executed, and let the size of lst be n.

Suppose we have a list of size n. In the worst case, sequential search needs n comparisons, and binary search on a sorted list needs approximately log base 2 of n.

Algorithms with a polynomial efficiency (constant, linear, square, cube, and so on) are said to run in a reasonable amount of time. They can be executed quickly on a modern processor.

However, there exist important and practical problems for which there is no known polynomial time algorithm. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.