WHAT IS AN ALGORITHM?

An algorithm refers to a method that can be used by a computer for the

solution of a problem. An algorithm can be defined as:
An algorithm is a set of rules for carrying out calculation either by
hand or on a machine.
An algorithm is a finite step-by-step procedure to achieve a required
result.
An algorithm to be any well-defined computational procedure that
takes some values as input and produces some values as output. Thus
an algorithm is a sequence of computational steps that transform the
input into the output.
An algorithm is an abstraction of a program to be executed on a
physical machine (model of Computation).

 Every algorithm must satisfy the following:

Input

: Zero or more quantities that are externally applied

Output

: At least one quantity is produced.

Definiteness: Each instruction should be clear and unambiguous

Finiteness

: Algorithm terminates after finite number of steps for

all test cases.

Effectiveness: Steps must be sufficiently simple and basic.

PSEUDOCODE
Pseudocode is a generic way of describing an algorithm without use of
any specific programming language syntax. As the name suggests, it
cannot be executed on a real computer, but it models and resembles real
programming code.
Pseudocode consists of short, English phrases used to explain specific
tasks within a programs algorithm and there is no real formatting or
syntax rules.
It is an efficient and environment-independent description of the key
principles of an algorithm.
The purpose of using Pseudocode is that it is easier for humans to
understand than conventional programming language code.
It is commonly used in textbooks and scientific publications that are
documenting various algorithms.
Pseudocode cannot be compiled and executed.

 The benefit of pseudocode is that it enables the programmer to

concentrate on the algorithms without worrying about all the syntactic
details of a particular programming language.

PROGRAM
A program is a language specific implementation of the algorithm. A
program is Synonymous with Code.
Every computer program is simply a series of instructions in a specific
order, designed to perform a specific task. A solution for a given problem
may be in the form of an algorithm or a program. An algorithm when
expressed in some programming language is called a program.

Figure 1.

WHY STUDY ALGORITHMS?

The study of algorithms provides a good understanding of algorithm
design which is a central element to a good understanding of
computer science and good programming.

 The study of algorithms is necessary from the following point of

views.

Algorithms help us to understand scalability.

Efficient algorithms lead to efficient programs.

The main factor to good program design is good algorithm

design.

Efficient programs make better use of hardware.

Study of algorithms helps us to design an efficient algorithm for the

given problem. The performance of the program depends on choosing
efficient algorithm so by designing the efficient algorithm we can also
increase the performance
Main Issues Related to algorithms
1. How to design algorithms
Appropriate planning is required while constructing algorithm because
proper Planning make algorithm to the point, accurate, efficient and when
convert this algorithm in to program it will result into small and high
performance program.

2. How to validate algorithms

Once an algorithm is planned, it is necessary to show that it computes the
correct

answer for all possible legal input in finite number of steps.

3. How to analyze algorithms

Analysis of algorithm is required to dictate the correctness and measure the
quantitative efficiency of an algorithm. When any algorithm is converting
into program and is executed, it uses the computers CPU to perform
4

operation and memory to holds the program and data. Analysis of

algorithms or performance analysis refer to the task determining how much
computing time and storage is requires.
4. How to test a program
The testing of a program includes debugging and performance
measurement. The performance measurement is the process of executing
correct program on data sets and measuring the time and space it takes to
compute the results.

CHARACTERISTICS OF AN ALGORITHM
The main characteristics of an algorithm are given below
Correctness
Efficiency
Simplicity
Generality
Non-ambiguity
Correctness
Once an algorithm has been designed, we have to prove its correctness.
This task can be accomplished by analyzing the algorithm that yields
the required results for every genuine input in a finite amount of time.
A common technique for proving the correctness of an algorithm is to
use the mathematical induction.
Proof of correctness is quite easy for some algorithm but it can be
quite complex for the others.

Efficiency
Efficiency is used to describe properties of an algorithm relating to
how much of various types of resources it consumes.
There are two kinds of algorithm efficiency: time efficiency and space
efficiency. Time efficiency indicates how fast the algorithm runs and
the space efficiency indicates how much memory the algorithm needs.
Simplicity
The simpler algorithms are easier to understand and easier to
implement.
The simplicity of an algorithm leads to a (very) flexible, efficient,
readable, small program. For few cases simpler algorithms are more
efficient than complex one but it is not always true.
For example: The Euclids algorithm is simpler than the middle
school procedure for calculating gcd (m, n)
Generality
The algorithm must be general to solve the problem. For example if
any algorithm is used to calculate the sum of first ten natural number
than it should be possible to calculate the sum of n natural numbers
when generalized.
Generality specified that algorithm should work for all valid sets of
input. It should be possible that the algorithm accept the range of
inputs that is natural for the problem.
There are some situations where the designing a general algorithm is
unnecessary or difficult or even impossible. For example: the standard
6

formulas for roots of a quadratic equation can not be generalized to

handle polynomials of arbitrary degrees.
Non-ambiguity
The operations in an algorithm have to be rigorously specified, i.e.
without ambiguities.
ANALYSIS OF ALGORITHMS
Analysis of an algorithm is requires to dictate the Correctness and
Measure the quantitative efficiency of an Algorithm. It includes.
Tracing of algorithm steps to specify logical correctness.
Space and time complexity measurement in terms of asymptotic order
of growth of functions.
The performance of the algorithm depends on two main factors, the
amount of computer memory consumed and the time required for
successfully execution of the algorithm.
There are two ways to analyze the performance of an algorithm;
First method is to carry out experiments using the various data sets
after implementation of algorithm in any programming language and
recording the amount of memory consumed and time required to
execute it.
Another method is used before implementation is called analytical
method in which we can approximately find out the space and time
required by the algorithm.

Cases Consider During the Analysis of Algorithm

During the analysis of an algorithm, there are three different cases are as
follows.
Best-Case
Average-Case
Worst-Case
Worst case complexity:
The worst case complexity of the algorithm is the function defined by the
maximum number of steps taken on any instance of size n.
This represents the input set that allows an algorithm to perform most
slowly. For example, for a searching algorithm, the worst case is one
where the value is in the last place or is not in the list.

Best case complexity:

The best case complexity of the algorithm is the function defined by the
minimum number of steps taken on any instance of size n.
This represents the input set that allows an algorithm to perform most
quickly.
For example, for a searching algorithm the best case would be if the
value we are searching for is found at the first location that the search
algorithm checks. This algorithm would need only one comparison.
Searching in the best case will result in a constant time of 1.
Average-case complexity:
The average-case complexity of the algorithm is the function defined by
an average number of steps taken on any instance of size n.
UNITS FOR MEASURING RUNNING TIME
There are usually two main methods of measuring the running time of an
algorithm.
One is a mathematical analysis of the algorithm, called an asymptotic
analysis, which can provides gross aspects of efficiency for all
possible inputs but not exact execution times.
On the other hand second approach is called an empirical analysis of
an actual implementation to determine exact running times for a
sample of specific inputs, but with this method we can not predict the
performance of the algorithm for all inputs.

UNITS FOR MEASURING RUNNING TIME

To measure the running time of a program implementing the algorithm in
any programming language, the real time measurement unit as a second,
a millisecond, can not be used, because absolute running times of a
program is dependent on the following factors:
The speed of a particular computer.
The quality of a program implementing the algorithm.
The compiler used in generating the machine.
Processor dependent (clock rate).
Environment dependent (single user vs. multi-user).
We can say that the absolute running times of programs implementing
the algorithms are not a good measure of efficiency.
The RAM Model of Computation
To analyze the algorithm, we have to count the number of basic operation
executed, this is only possible if we agree on a certain model of
computation. Here we choose a computational model called the Random
Access Machine (RAM ) model with the following :
A generic one processor;
The instructions are executed one after another, with no concurrent
operation.
Memory words have fixed constant size;
Direct/indirect memory access;

10

 All memory accesses take the same amount of time.

All atomic data (chars, ints, doubles, pointers, etc.) take unit space
Basic operations like memory access, arithmetic (+, , *, /, %, floor,
ceiling etc.), and control (conditional and unconditional branch,
subroutine call and return). Each such instruction takes a constant
amount of time (i.e. cost 1) called the unit cost of measuring.
The unit cost measure is independent of processor speed.
We can focus on some important operations called the basic
operations of the algorithms, which dominate the running time.

For Example,

In sorting: only count comparisons and data movements.

In matrix multiplication: only count the multiplication and
addition
In polynomial evaluation : only count the multiplication
and addition.
In recursive programs: only count recursive calls.

Let ci is the execution time of the basic operation of an algorithm and f

(n) be the number of times this operation to be executed.

Then the running time T (n) of the algorithm can be calculate by the
formula.

T (n) ci* f (n)

ASYMPTOTIC NOTATION

11

Asymptotic means a line tends to converge to a curve, which may or may

not eventually touch the curve. It is a line that says within bounds.

Time and space complexity is measured in terms of asymptotic notations.

Asymptotic notation can describe the time and space complexity accurately
for large instance characteristics.

For a given algorithm asymptotic notation will provides upper and /or lower
time and space bounds. Upper bound gives the maximum time / space
required and lower bound gives the minimum time / space required.
A tool for analyzing time and space usage of algorithms
Assumes input size is a variable, say n, and gives time and space
bounds as a function of n
Provides simple characterization of an algorithm efficiency
Ignores multiplicative and additive constants.
Compare the growth rates of two expressions of running time.
Concerned only with the rate of growth.

12

13