Analysis of algorithm

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a

certain order to get the desired output. Algorithms are generally created independent of
underlying languages, i.e. an algorithm can be implemented in more than one programming
language.
From the data structure point of view, following are some important categories of algorithms −
• Search − Algorithm to search an item in a data structure.
• Sort − Algorithm to sort items in a certain order.
• Insert − Algorithm to insert item in a data structure.
• Update − Algorithm to update an existing item in a data structure.
• Delete − Algorithm to delete an existing item from a data structure.

An algorithm is the best way to represent the solution of a particular problem in a very simple
and efficient way. If we have an algorithm for a specific problem, then we can implement it in
any programming language, meaning that the algorithm is independent from any
programming languages.

Algorithm Design

The important aspects of algorithm design include creating an efficient algorithm to solve a
problem in an efficient way using minimum time and space.
To solve a problem, different approaches can be followed. Some of them can be efficient with
respect to time consumption, whereas other approaches may be memory efficient. However, one
has to keep in mind that both time consumption and memory usage cannot be optimized
simultaneously. If we require an algorithm to run in lesser time, we have to invest in more memory
and if we require an algorithm to run with lesser memory, we need to have more time.

Problem Development Steps

The following steps are involved in solving computational problems.

• Problem definition
• Development of a model
• Specification of an Algorithm
• Designing an Algorithm
 • Checking the correctness of an Algorithm
• Analysis of an Algorithm
• Implementation of an Algorithm
• Program testing
• Documentation

Characteristics of Algorithms

The main characteristics of algorithms are as follows −

• Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or
phases), and their inputs/outputs should be clear and must lead to only one meaning.
• Input − An algorithm should have 0 or more well-defined inputs.
• Output − An algorithm should have 1 or more well-defined outputs, and should match the
desired output.
• Finiteness − Algorithms must terminate after a finite number of steps.
• Feasibility − Should be feasible with the available resources.
• Independent − An algorithm should have step-by-step directions, which should be
independent of any programming code.

Difference between Algorithm and Pseudocode

An algorithm is a formal definition with some specific characteristics that describes a process,
which could be executed by a Turing-complete computer machine to perform a specific task.
Generally, the word "algorithm" can be used to describe any high level task in computer science.
On the other hand, pseudocode is an informal and (often rudimentary) human readable description
of an algorithm leaving many granular details of it. Writing a pseudocode has no restriction of
styles and its only objective is to describe the high level steps of algorithm in a much realistic
manner in natural language.

Analysis of algorithm

Efficiency of an algorithm can be analyzed at two different stages, before implementation and
after implementation. They are the following −
 • A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an
algorithm is measured by assuming that all other factors, for example, processor speed,
are constant and have no effect on the implementation.
• A Posterior Analysis − This is an empirical analysis of an algorithm. The selected
algorithm is implemented using programming language. This is then executed on target
computer machine. In this analysis, actual statistics like running time and space required,
are collected.
We shall learn about a priori algorithm analysis. Algorithm analysis deals with the execution or
running time of various operations involved. The running time of an operation can be defined as
the number of computer instructions executed per operation.

Algorithm Complexity

Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm
X are the two main factors, which decide the efficiency of X.
• Time Factor − Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm.
• Space Factor − Space is measured by counting the maximum memory space required by
the algorithm.
The complexity of an algorithm f(n) gives the running time and/or the storage space required by
the algorithm in terms of n as the size of input data.

Space Complexity

Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following
two components −
• A fixed part that is a space required to store certain data and variables, that are independent
of the size of the problem. For example, simple variables and constants used, program
size, etc.
• A variable part is a space required by variables, whose size depends on the size of the
problem. For example, dynamic memory allocation, recursion stack space, etc.
Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and S(I)
is the variable part of the algorithm, which depends on instance characteristic I. Following is a
simple example that tries to explain the concept −
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop
Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now, space
depends on data types of given variables and constant types and it will be multiplied accordingly.

Time Complexity

Time complexity of an algorithm represents the amount of time required by the algorithm to run
to completion. Time requirements can be defined as a numerical function T(n), where T(n) can
be measured as the number of steps, provided each step consumes constant time.
For example, addition of two n-bit integers takes n steps. Consequently, the total computational
time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, we observe that
T(n) grows linearly as the input size increases.

Asymptotic Analysis

Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of

its run-time performance. Using asymptotic analysis, we can very well conclude the best case,
average case, and worst case scenario of an algorithm.
Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work
in a constant time. Other than the "input" all other factors are considered constant.
Asymptotic analysis refers to computing the running time of any operation in mathematical units
of computation. For example, the running time of one operation is computed as f(n) and may be
for another operation it is computed as g(n2). This means the first operation running time will
increase linearly with the increase in n and the running time of the second operation will increase
exponentially when n increases. Similarly, the running time of both operations will be nearly the
same if n is significantly small.
Usually, the time required by an algorithm falls under three types −

• Best Case − Minimum time required for program execution

• Average Case − Average time required for program execution.
• Worst Case − Maximum time required for program execution.
Introduction to Asymptotic Notations

1. What is Asymptotic Notations?

Asymptotic Notations are languages that allow us to analyze an algorithm’s run-time

performance. Asymptotic Notations identify running time by algorithm behavior as the input size
for the algorithm increases. This is also known as an algorithm’s growth rate. Usually, the time
required by an algorithm falls under three types −

Types of Asymptotic Notation

Following are the commonly used asymptotic notations to calculate the running time complexity
of an algorithm.

• Ο Notation (Big-O Notation)

• Ω Notation (Big-Omega Notation)
• θ Notation (Theta Notation)

2.1 Ο Notation (Big-O Notation)

Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or the longest
amount of time an algorithm can possibly take to complete.. It provides us with an asymptotic
upper bound for the growth rate of run-time of an algorithm.
For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }

2.2 Ω Notation (Big-Omega Notation)

Big-Omega, commonly written as Ω, is an Asymptotic Notation for the best case, or the best
amount of time an algorithm can possibly take to complete. It provides us with an asymptotic
lower bound for the growth rate of run-time of an algorithm.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }

2.3 θ Notation (Theta Notation)

Theta, commonly written as Θ, is an Asymptotic Notation to denote the asymptotically tight

bound (lower bound and the upper bound) on the growth rate of run-time of an algorithm.
For example, for a function f(n)

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

3. Common Asymptotic Notations

Following is a list of some common asymptotic notations −

Notation Name
O(1) constant
O(log n) logarithmic
O(n) linear
O(n log n) = O(log n!) linearithmic, loglinear, or quasilinear
O(n2) quadratic
O(nc) polynomial or algebraic
O(cn); where c>1 exponential
O(n!) factorial
4. Why Performance Analysis?

There are many important things that should be taken care of, like user friendliness, modularity,
security, maintainability, etc. Why to worry about performance?

The answer to this is simple, we can have all the above things only if we have performance. So
performance is like currency through which we can buy all the above things. Another reason for
studying performance is – speed is fun!

Methods for the design of efficient algorithm

Greedy Algorithms
An algorithm is designed to achieve optimum solution for a given problem. In greedy algorithm
approach, decisions are made from the given solution domain. As being greedy, the closest
solution that seems to provide an optimum solution is chosen.
Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally
optimized solutions. However, generally greedy algorithms do not provide globally optimized
solutions.
Examples
Most networking algorithms use the greedy approach. Here is a list of few of them −

• Travelling Salesman Problem

• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Graph - Map Coloring
• Graph - Vertex Cover
• Knapsack Problem
• Job Scheduling Problem

Divide and Conquer

In divide and conquer approach, the problem in hand, is divided into smaller sub-problems and
then each problem is solved independently. When we keep on dividing the subproblems into even
smaller sub-problems, we may eventually reach a stage where no more division is possible. Those
"atomic" smallest possible sub-problem (fractions) are solved. The solution of all sub-problems
is finally merged in order to obtain the solution of an original problem.
Broadly, we can understand divide-and-conquer approach in a three-step process.

Divide/Break

This step involves breaking the problem into smaller sub-problems. Sub-problems should
represent a part of the original problem. This step generally takes a recursive approach to divide
the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic
in nature but still represent some part of the actual problem.

Conquer/Solve

This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems
are considered 'solved' on their own.

Merge/Combine
When the smaller sub-problems are solved, this stage recursively combines them until they
formulate a solution of the original problem. This algorithmic approach works recursively and
conquer & merge steps works so close that they appear as one.
Examples
The following computer algorithms are based on divide-and-conquer programming approach −

• Merge Sort
• Quick Sort
• Binary Search
• Strassen's Matrix Multiplication
• Closest pair (points)

Dynamic Programming
Dynamic programming approach is similar to divide and conquer in breaking down the problem
into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-
problems are not solved independently. Rather, results of these smaller sub-problems are
remembered and used for similar or overlapping sub-problems.
Dynamic programming is used where we have problems, which can be divided into similar sub-
problems, so that their results can be re-used. Mostly, these algorithms are used for optimization.
Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the
previously solved sub-problems. The solutions of sub-problems are combined in order to achieve
the best solution.
So we can say that −
• The problem should be able to be divided into smaller overlapping sub-problem.
• An optimum solution can be achieved by using an optimum solution of smaller sub-
problems.
• Dynamic algorithms use Memoization.

Comparison

In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are
motivated for an overall optimization of the problem.
In contrast to divide and conquer algorithms, where solutions are combined to achieve an overall
solution, dynamic algorithms use the output of a smaller sub-problem and then try to optimize a
bigger sub-problem. Dynamic algorithms use Memoization to remember the output of already
solved sub-problems.
Example
The following computer problems can be solved using dynamic programming approach −

• Fibonacci number series

• Knapsack problem
• Tower of Hanoi
• All pair shortest path by Floyd-Warshall
• Shortest path by Dijkstra
• Project scheduling
Dynamic programming can be used in both top-down and bottom-up manner. And of course,
most of the times, referring to the previous solution output is cheaper than recomputing in terms
of CPU cycles.