# What is Algorithm? – Nutshell Explanation

## What is Algorithm?

Thealgorithmis a set of rules defined in specific order to do certain computation and carry out some predefined task. It is a step by step procedure to solve the problem.

Evolution of algorithm has gone through lone way. The term **Algorithm **was coined by the Persian mathematician **Al-Khwarizmi **in the ninth century.

Given the algorithm, it is easy to program the solution. It bridges the gap between natural language description of the solution and syntax of programming language. It is a set of rules which are used to solve real-life problems. It provides a loose form of a solution in a pseudo-programming language. We can treat it as a set of finite instructions which solves a particular problem when applied it is applied to that problem with legal inputs.

The first-ever algorithm was developed by Babylonians for factorization of a number and to find roots of the equation. Euclid had proposed a famous algorithm for finding Greatest Common Divisor (GCD) of two numbers.

Initially, the solution to the problem is thought as a natural language description, whose syntax is too far from the programming language. Before the actual problem solved in a programming language, natural language description of the solution is first represented as an algorithm. It is then converted to programming syntax. The process of solving a problem is depicted in following figure

If the algorithm is correct, then the program should produce correct output on valid input, otherwise, it should produce an appropriate error message. For example, to find the division A/B, correctly written program would return value of A/B for B > 0, and it would show the error message like “Invalid divisor” for B = 0.

## Properties of Algorithm

A good algorithm should have the following properties/characteristics:

**Input:** The algorithm may take zero or more input arguments. Depending on the problem, the input may be a scalar, vector, array, tree, graph or some other data structures

**Output: **The algorithm reads input, processes it and produces at least one output. Depending on the problem being solved, the output may of the form scalar, vector, array, tree, graph or some other data structures.

**Definiteness: **All instructions should be unambiguous and simple to interpret. There should not be multiple ways to interpret the same instruction. Each instruction should be precise and concise

**Finiteness: **Every algorithm must terminate after a finite number of steps. If the algorithm contains a loop, the upper bound of the loop must be finite. Recursive calls should have a well-defined base case for the termination

**Effectiveness: **The algorithm should be written with a basic set of instructions. The operations should be basic enough to perform exactly using a basic set, just like one can perform them with pen and paper. Complex operations should be performed using a combination of basic instruction. For example, multiplication should be performed using loop and addition, sorting should be carried out using looping, comparison, swapping etc.

## Types of Algorithmic Complexities

Algorithms are analyzed using two types of complexities

**Time complexity**: It is the amount of time taken by the algorithm to solve the given problem.

**Space complexity**: It is the amount of memory required by the algorithm to solve the given problem.

## Problems Solved by Algorithms

Algorithms are not developed just to solve problems like sorting, factorial, GCD etc. The scope of the algorithm is much wider than that. Few of the real-life problems are listed here for which the design of an efficient algorithm matters a lot

Such problems may not be solved effectively using traditional approaches and even if they are solvable, the answer may not be optimal or it may take a too long time. Various class of algorithms are :

**String matching algorithms**: Can be useful in text search, editors, compilers etc.**Number theory and numerical algorithms**: Useful in the statistical analysis of data.**Divide and conquer**: Used to solve sorting, convex hull, min-max problem.**Linear programming**: Can be useful in solving many optimization problems.**Dynamic programming**: Solves the optimization problems like subsequence, super sequence, assembly line scheduling, cruise scheduling etc.**Greedy methods**: Provides a suboptimal solution to the problems like make a change, minimum spanning tree, Huffman code, job sequencing etc.**Sorting**: Useful to sort numerical or string data.

However, the list is far more exhaustive, but we listed here a few of the most common problems appear in real life.

## How to Write Algorithm?

The algorithm consists of two parts:

Head and body. Head part consists of name, description of the problem being solved, input to the problem and expected output. It may also include the explanation of the input argument and output variable. The description provides a clear idea to the user about the functionality of the algorithm.

Body part includes a logical sequence of statements involving various constructs like conditional statements, expressions, loops, breaks, function calls etc.

An algorithm is a lucid form of program and it does not have rigid restrictions on the syntax. One can write it using his own terminology and syntax

However, some of the common rules followed for writing algorithms, which are stated below :

- The algorithm should start with the keyword
**Algorithm**, followed by its name, followed by a list of arguments to be passed.

**Algorithm** FIND_SUM(A, B)

- Comments start with // sign. In the very next line, we should specify the description and input-output.

```
// Problem Description : Add two integer numbers.
// Input: Two numbers A and B on which sum is to be performed.
// Output: Sum of given two numbers.
```

- Next comes the body part, which contains various logical statements in the proper sequence. These statements may contain control statements, loops, expressions etc.
- Compound statements are enclosed within the opening and closing curly brace i.e. { … }
- Use the left arrow for assignment

`C ← A + B`

- Array index usually starts with index 0 or 1.
- Relational operations are performed using relational operators like <, >, ==, !=, ?= and <=
- Logical operations are performed using logical operators like
**and****or**and**not** - Input and output are performed using read and write a statement.

```
read (A) / read “A”
write (A) / write “A”
print (A) / print “A”
```

- Control statements are written as follows :

**if **(condition) **then **
Statements
**end**

**if** (condition) **then **
Statements
**else**
Statements
**end**

- Multiple statements are enclosed within { … }
- While loop is written as follows :

**while **(condition) **do**
{
Do some work
}

- Sometimes curly braces are omitted and a block is closed with the
**end**keyword

**while **(condition) **do**
Do some work
**end**

- For loop is written as follows:

**for **index ← FirstIndex to LastIndex **do**
{
Do some work
}

- Sometimes curly braces are omitted and a block is closed with the
**end**keyword

**for **index ← FirstIndex to LastIndex **do**
Do some work
**end**

## Examples:

**Write an algorithm for finding the factorial of number n**.

**Algorithm **FACTORIAL(n)
// Description: Find factorial of a given number
// Input: Number n whose factorial is to be computed
// Output : Factorial of n = n x (n – 1) x … x 2 x 1
**if **(n == 1) **then**
return 1
**else**
return n * FACTORIAL(n – 1)
**end**

**Write an algorithm to perform matrix multiplication**

**Algorithm **MATRIX_MULTIPLICATION(A, B)
// Description: Perform matrix multiplication of two matrices.
// Input : Two matrices A and B of size n x n.
// Output : Resultant matrix containing multiplication of A and B
**for **i ← 1 to n **do**
**for **j ← 1 to n **do**
C[i][j] ← 0
**for **k ← 1 to n **do**
C[i][j] ← C[i][j] + A[i][k] * B[k][j]
** end
end
end
**

However, there is no strict rule to follow these standards. Its syntax may vary from person to person.

**Additional Resource**: History of development of algorithm

Superb explained

Thanks for interaction and showing interest

Simply Super…

Thank you very much Shivang