### Definition

• An algorithm is a set of sequential step by step procedure, each of which has a clear-cut meaning and usually written in ordinary/natural English Language to solve a given problem in finite number of steps.
• An algorithm is defined as a complete, unambiguous, finite number
of logical steps for solving a specific problem.

### Characteristics/Properties

Every algorithm must satisfy the following criteria i.e. a typical algorithm has following characteristics –

(i) Input: An algorithm must take at least one or more input values.

(ii) Output: An algorithm must provide at least one or more output values.

(iii) Definiteness : No instructions should be repeated i.e. each step of the algorithm must be precisely and unambiguously stated.

(iv) Finiteness : An algorithm must terminate in a finite number of steps.

(v) Effectiveness : An algorithm should be simple and focused on its main objectives. Each step in algorithm must be effective.

(vi) Generality : The algorithm must be complete in itself so that it can be used to solve problems of a specific type for any input data.

### Features

• No matter what the input values are, an algorithm terminates after executing a finite number of instructions.
• It may be possible to solve to problem in more than one ways, resulting in more than one algorithm. The best choice of various algorithms depends on the factors like reliability, accuracy and easy to modify. The most important factor in the choice of algorithm is the time requirement to execute it, after writing code in High-level language with the help of a computer.
• The algorithm which will need the least time when executed is considered the best.

• The algorithms are very easy to understand.
• Algorithm is programming language independent.
• Algorithm makes the problem simple, clear, correct and effective.

### Classification

If ‘n’ is the number of data items to be processed or degree of polynomial or the size of the file
to be sorted or searched or the number of nodes in a graph etc. They may be of following categories –

1  –

Next instructions of most programs are executed once or at most only a few times. If all the         instructions of a program have this property, we say that its running time is a constant.

Log n  –

• When the running time of a program is logarithmic, the program gets slightly slower as n grows.
• This running time commonly occurs in programs that solve a big problem by transforming it into a smaller problem, cutting the size by some constant fraction.,
• When n is a million, log n is a doubled whenever n doubles, log n increases by a constant, but log n does not double until n increases to n2.

n

• When the running time of a program is linear, it is generally the case that a small amount of processing is done on each input element.
• This is the optimal situation for an algorithm that must process n inputs.

n. log n

• This running time arises for algorithms but solve a problem by breaking it up into smaller sub-problems, solving them independently, and then combining the solutions. When n doubles, the running time more than doubles.

n2

• When the running time of an algorithm is quadratic, it is practical for use only on relatively small problems.
• Quadratic running times typically arise in algorithms that process all pairs of data items (perhaps in a double nested loop) whenever n doubles, the running time increases four fold.

n3

• Similarly, an algorithm that process triples of data items (perhaps in a triple– nested loop) has a cubic running time and is practical for use only on small problems. Whenever n doubles, the running time increases eight fold.

2n

• Few algorithms with exponential running time are likely to be appropriate for practical use, such algorithms arise naturally as “brute–force” solutions to problems. Whenever n doubles, the running time squares.

The most common computing order of complexity are –
O(1),  O(log2 n),  O(n),  O(n. log2 n),  O(n2),  O(n3),  O(2n),  n! and nn

298 total views,  1 views today

Categories: Algorithm & Design