Algorithm

In computer programming terms, an algorithm is a set of well-defined instructions to solve a

particular problem. It takes a set of input and produces a desired output. For example,

An algorithm to add two numbers:

1. Take two number inputs

2. Add numbers using the + operator
3. Display the result

Qualities of Good Algorithms

 Input and output should be defined precisely.

 Each step in the algorithm should be clear and unambiguous.
 Algorithms should be most effective among many different ways to solve a problem.
 An algorithm shouldn't include computer code. Instead, the algorithm should be
written in such a way that it can be used in different programming languages.

Algorithm 1: Add two numbers entered by the user

 Step 1:
Start
 Step 2:
Declare variables num1, num2 and sum.
 Step 3:
Read values num1 and num2.
 Step 4:
Add num1 and num2 and assign the result to sum.
 sum←num1+num2
 Step 5: Display sum
 Step 6: Stop

Characteristics of an Algorithm
The following are the characteristics of an algorithm:

o Input: An algorithm has some input values. We can pass 0 or some input
value to an algorithm.

o Output: We will get 1 or more output at the end of an algorithm.

o Unambiguity: An algorithm should be unambiguous which means that the

instructions in an algorithm should be clear and simple.

o Finiteness: An algorithm should have finiteness. Here, finiteness means that

the algorithm should contain a limited number of instructions, i.e., the
instructions should be countable.
 o Effectiveness: An algorithm should be effective as each instruction in an
algorithm affects the overall process.

o Language independent: An algorithm must be language-independent so

that the instructions in an algorithm can be implemented in any of the
languages with the same output.

Dataflow of an Algorithm

o Problem: A problem can be a real-world problem or any instance from the

real-world problem for which we need to create a program or the set of
instructions. The set of instructions is known as an algorithm.

o Algorithm: An algorithm will be designed for a problem which is a step by

step procedure.

o Input: After designing an algorithm, the required and the desired inputs are
provided to the algorithm.

o Processing unit: The input will be given to the processing unit, and the
processing unit will produce the desired output.

o Output: The output is the outcome or the result of the program.

The major categories of algorithms are given below:

o Sort: Algorithm developed for sorting the items in a certain order.

o Search: Algorithm developed for searching the items inside a data structure.

o Delete: Algorithm developed for deleting the existing element from the data
structure.

o Insert: Algorithm developed for inserting an item inside a data structure.

o Update: Algorithm developed for updating the existing element inside a data
structure.

Algorithm Analysis
The algorithm can be analyzed in two levels, i.e., first is before creating the
algorithm, and second is after creating the algorithm. The following are the two
analysis of an algorithm:

o Priori Analysis: Here, priori analysis is the theoretical analysis of an algorithm

which is done before implementing the algorithm. Various factors can be
considered before implementing the algorithm like processor speed, which
has no effect on the implementation part.
 o Posterior Analysis: Here, posterior analysis is a practical analysis of an
algorithm. The practical analysis is achieved by implementing the algorithm
using any programming language. This analysis basically evaluate that how
much running time and space taken by the algorithm.

Algorithm Complexity
The performance of the algorithm can be measured in two factors:

o Time complexity: The time complexity of an algorithm is the amount of time

required to complete the execution. The time complexity of an algorithm is
denoted by the big O notation. Here, big O notation is the asymptotic notation
to represent the time complexity. The time complexity is mainly calculated by
counting the number of steps to finish the execution. Let's understand the
time complexity through an example.

1. sum=0;
2. // Suppose we have to calculate the sum of n numbers.
3. for i=1 to n
4. sum=sum+i;
5. // when the loop ends then sum holds the sum of the n numbers
6. return sum;

In the above code, the time complexity of the loop statement will be atleast n, and if
the value of n increases, then the time complexity also increases. While the
complexity of the code, i.e., return sum will be constant as its value is not dependent
on the value of n and will provide the result in one step only. We generally consider
the worst-time complexity as it is the maximum time taken for any given input size.

o Space complexity: An algorithm's space complexity is the amount of space

required to solve a problem and produce an output. Similar to the time
complexity, space complexity is also expressed in big O notation.

For an algorithm, the space is required for the following purposes:

1. To store program instructions

2. To store constant values

3. To store variable values

4. To track the function calls, jumping statements, etc.

 Auxiliary space: The extra space required by the algorithm, excluding the input size,
is known as an auxiliary space. The space complexity considers both the spaces, i.e.,
auxiliary space, and space used by the input.

So,

Space complexity = Auxiliary space + Input size.

Asymptotic Notations
Asymptotic notations are the mathematical notations used to describe the running time
of an algorithm when the input tends towards a particular value or a limiting value.

For example: In bubble sort, when the input array is already sorted, the time taken by the
algorithm is linear i.e. the best case.

But, when the input array is in reverse condition, the algorithm takes the maximum time
(quadratic) to sort the elements i.e. the worst case.

When the input array is neither sorted nor in reverse order, then it takes average time.
These durations are denoted using asymptotic notations.

There are mainly three asymptotic notations:

 Big-O notation

 Omega notation

 Theta notation

Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an algorithm. Thus, it
gives the worst-case complexity of an algorithm.

Big
-O gives the upper bound of a function
O(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

The above expression can be described as a function f(n) belongs to the set O(g(n)) if
there exists a positive constant c such that it lies between 0 and cg(n) , for sufficiently
large n .
For any value of n , the running time of an algorithm does not cross the time provided
by O(g(n)) .

Since it gives the worst-case running time of an algorithm, it is widely used to analyze an
algorithm as we are always interested in the worst-case scenario.

Omega Notation (Ω-notation)

Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.

Omega gives the lower bound of a function

Ω(g(n)) = { f(n): there exist positive constants c and n0

such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

The above expression can be described as a function f(n) belongs to the set Ω(g(n)) if
there exists a positive constant c such that it lies above cg(n) , for sufficiently large n .
For any value of n , the minimum time required by the algorithm is given by
Omega Ω(g(n)) .

Theta Notation (Θ-notation)

Theta notation encloses the function from above and below. Since it represents the
upper and the lower bound of the running time of an algorithm, it is used for analyzing
the average-case complexity of an algorithm.
 Theta bounds
the function within constants factors

For a function g(n) , Θ(g(n)) is given by the relation:

Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0

such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }

The above expression can be described as a function f(n) belongs to the set Θ(g(n)) if
there exist positive constants c1 and c2 such that it can be sandwiched
between c1g(n) and c2g(n) , for sufficiently large n.
If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n ≥ n0 , then f(n) is
said to be asymptotically tight bound.