_{References used for this section: C}

Algorithms usually have a primary parameter which we will call . This is basically the input size (i.e the number of data items to be processed) and can be anything like:

- The degree of a polynomial
- The size of a file on which sorting or searching needs to be done
- The number of nodes in a graph etc.

Algorithms can be classified with to the functions their running times are proportional to. Most common algorithms have running times proportional to one of the following functions (in descending order of efficiency):

**Constant**. All the instructions in the algorithm are executed once or at most a few times. (define ‘a few’ precisely?) These algorithms are the most efficient.**Logarithmic ( )**. When doubles, the running time of these algorithms increase by a constant. When increases to , the running time doubles.**Linear ( )**. When doubles, the running time doubles also.**Log-Linear ( )**. When doubles, the running time more than doubles (but only slightly).**Quadratic ( )**. When doubles, the running time quadruples.**Cubic ( )**. When doubles, the running time increases eight times.**Exponential ( )**. When doubles, the running time squares. These are hopelessly slow algorithms.

To summarise, the running time of common algorithms is usually an element of:

- .

Advertisements