Unit - I

Introduction to Algorithm
1 and Data Structures

Syllabus
Introduction : From Problem to Program (Problem, Solution, Algorithm, Data Structure and
Program). Data Structures : Data, Information, Knowledge, and Data structure, Abstract Data Types
(ADT), Data Structure Classification (Linear and Non-linear, Static and Dynamic, Persistent and
Ephemeral data structures).
Algorithms : Problem Solving, Introduction to algorithm, Characteristics of algorithm, Algorithm
design tools : Pseudo-code and flowchart. Complexity of algorithm : Space complexity, Time
complexity, Asymptotic notation- Big-O, Theta and Omega, Finding complexity using step count
method, Analysis of programming constructs-Linear, Quadratic, Cubic, Logarithmic.
Algorithmic Strategies : Introduction to algorithm design strategies - Divide and Conquer, and
Greedy strategy.

Contents
1.1 From Problem to Data Structure (Problem, Logic, Algorithm, and Data Structure)
1.2 Data Structures : Data, Information, Knowledge, and Data Structure
1.3 Abstract Data Types (ADT). . . . . . . . . . . . . . . Dec.-10, 11,
. . . . . . . . . . . . . . . . . May-10, 11, 12, 13, 19, · · · · · · Marks 6
1.4 Data Structure Classification . . . . . . . . . . . . . May-17, Dec.-18, 19, · · · · · · · · Marks 4
1.5 Problem Solving . . . . . . . . . . . . . . . . . Dec.-09, 10, May-10, 11, · · · · Marks 12
1.6 Difficulties in Problem Solving . . . . . . . . . . . . Dec.-10, May-16, · · · · · · · · · · · Marks 4
1.7 Introduction to Algorithm. . . . . . . . . . . . . . . . . Dec.-16, May-18, 19, · · · · · · · · Marks 4
1.8 Algorithm Design Tools . . . . . . . . . . . . . . . . . May-10, 11, Dec.-10, · · · · · · · · Marks 8
1.9 Step Count Method
1.10 Complexity of Algorithm . . . . . . . . . . . . . . . . . Dec.-09, 10, 11, 19,
. . . . . . . . . . . . . . . . . May-12, 13, · · · · · · · · · · · · · · · Marks 8
1.11 Asymptotic Notations . . . . . . . . . . . . . . . . . Dec.-09, 10, 11, 16, 17, 19,
. . . . . . . . . . . . . . . . . May-10, 12, 13, 18, 19, · · · · · · Marks 8
1.12 Analysis of Programming Constructs . . . . . . . May-10, 13, 14, Dec.-11, 13, · · Marks 8
1.13 Recurrence Relation . . . . . . . . . . . . . . . . . Dec.-18, · · · · · · · · · · · · · · · · · · Marks 2
1.14 Solving Recurrence Relation
1.15 Best, Worst and Average Case Analysis
1.16 Introduction to Algorithm Design Strategies . . May-17, 18, Dec.-17, 19, · · · · · Marks 6

(1 - 1)
Fundamentals of Data Structures 1-2 Introduction to Algorithm and Data Structures

Part I : Introduction to Data Structures

1.1 From Problem to Data Structure (Problem, Logic, Algorithm,

and Data Structure)
· Problem can be solved using series of actions. The steps that are followed in order
to solve the problem are collectively called as algorithm.
· There are some problems for which the direct solution does not exist. For building
the solution to such problems some reasoning is required. This reasoning is
usually based on knowledge and prior experience. Hence the process of trial and
error is followed to solve the given problem. This process is called logic building
for particular solution.
· For example – For displaying the list of numbers in reverse direction, we should
read and display the last element of the list, then last but one and so on.
· In computer science, when we want to solve any problem, then we need Data, the
data structure that will arrange the data in some specific manner and the
algorithm which will handle this data structure in some systematic manner.
· Data structure is the means by which we can model the problem.
· For example - Arrays - It contains integer elements(data) which are arranged in
sequential organization (data structure) and then algorithms such as - addition of
all elements, or for sorting the elements in specific manner are applied on this
data structure.
· Thus Data structure is used for arranging the data and algorithm is used to solve
the problem by systematic execution of each step.

1.2 Data Structures : Data, Information, Knowledge,

and Data Structure
Data : Data refers to raw data or unprocessed data.
Information : Information is data that has been processed in such a way that it will
become meaningful to the person who receives it. The information has structure and
context.
Knowledge : Knowledge is basically something which person knows. Knowledge
requires a person to understand what information is, based on their experience and
knowledge base
Data structure : A data structure is a particular way of organizing data in a
computer so that it can be used effectively.
For example – Consider set of elements which can be stored in array data structure.
The representation of array containing set of elements is as follows –
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-3 Introduction to Algorithm and Data Structures

0 1 2 3 4

10 20 30 40 50

Any element in above array can be referred by an index. For instance the element 40
can be accessed as array[3].

Difference between Data and Information

Sr. No. Data Information

1. Data is in raw form. Information is processed form of
data.
2. Data may or may not be Information is always meaningful.
meaningful.
3. Data may not be in some Information generally follows specific
specific order. ordering.
4. For example - each Student's For example - The average score of a
marks in exam is one piece of class is information that can be
data. derived from given data.

1.3 Abstract Data Types (ADT)

SPPU : Dec.-10, 11, May-10, 11, 12, 13, 19, Marks 6

The abstract data type is a triple of D - Set of domains, F - Set of functions,

A - axioms in which only what is to be done is mentioned but how is to be done is not
mentioned.
In ADT, all the implementation details are hidden. In short

ADT = Type + Function names + Behavior of each function

We will discuss in further chapters how the ADT can be written

1.3.1 Realization of ADT

The abstract datatype consists of following things
1. Data used along with its data type.
2. Declaration of functions which specify only the purpose. That means "What is to be
done" in particular function has to be mentioned but "how is to be done" must be
hidden.
3. Behavior of function can be specified with the help of data and functions together.
Thus ADT allows programmer to hide the implementation details. Hence it is called
abstract. For example : If we want to write ADT for a set of integers, then we will use
following method
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-4 Introduction to Algorithm and Data Structures

AbstractDataType Set {
Instances : Set is a collection of integer type of elements.
Preconditions : none
Operations :
1. Store ( ) : This operation is for storing the integer element in a set.
2. Retrieve ( ) : This operation is for retrieving the desired element from the given
set.
3. Display ( ) : This operation is for displaying the contents of set.
}
There is a specific method using which an ADT can be written. We begin with
keyword AbstractDataType which is then followed by name of the data structure for
which we want to write an ADT. In above given example we have taken Set data
structure.
· Then inside a pair of curly brackets ADT must be written.
· We must first write instances in which the basic idea about the corresponding
data structure must be given. Generally in this section definition of corresponding
data structure is given.
· Using Preconditions or Postconditions we can mention specific conditions that
must be satisfied before or after execution of corresponding function.
· Then a listing of all the required operations must be given. In this section, we
must specify the purpose of the function. We can also specify the data types of
these functions.

1.3.2 ADT for Arrays

AbstractDataType Array
{
Instances : An array A of some size, index i and total number of elements in the
array n.
Operations :
Store () – This operation stores the desired elements at each successive location.
display () – This operation displays the elements of the array.
}

Review Questions

1. Explain what is abstract data type ? SPPU : Dec.-10, Marks 4

2. What is ADT ? Write ADT for an arrays.

SPPU : May-10,11, Dec.-11, Marks 6, May-12, Marks 4

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-5 Introduction to Algorithm and Data Structures

3. Explain following terminologies : i) Data type ii) Data structure iii) Abstract data type.
SPPU : May-13, Marks 6

4. Define (1) ADT (2) Data Structure. SPPU : May-19, Marks 2

1.4 Data Structure Classification SPPU : May-17, Dec.-18, 19, Marks 4

The data structures can be divided into two basic types primitive data structure and
non primitive data structure. The Fig. 1.4.1. shows various types of data structures.

Data structure

Primitive data Non primitive data

structures structures
example : int, char, float

Linear data Non linear data

structures structures
example : lists, example : trees,
stacks, queues graphs

Fig. 1.4.1 Classification of data structure

1.4.1 Linear and Non linear Data Structure

Linear data structures are the data structures in which data is arranged in a list or in
a straight sequence.
For example : arrays, list.
Non linear data structures are the data structures in which data may be arranged in
hierarchical manner.
For example : trees, graphs.

1.4.2 Static and Dynamic Data Structure

The static data structures are data structures having fixed size memory utilization.
One has to allocate the size of this data structure before using it.
For example (Static Data Structure) :
Arrays in C is a static data structure. We first allocate the size of the arrays before
its actual use. Sometimes what ever size we have allocated for the arrays may get
wasted or we may require larger than the one which is existing. Thus the data structure
is static in nature.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-6 Introduction to Algorithm and Data Structures

The dynamic data structure is a data structure in which one can allocate the memory
as per his requirement. If one does not want to use some block of memory, he can
deallocate it.
For example (Dynamic Data Structure (Dynamic)) :
Linked list, the linked list is a collection of many nodes. Each node consists of data
and pointer to next node. In linked list user can create as much nodes (memory) as he
wants, he can dellocate the memory which cannot be utilized further.
The advantage of dynamic data structure over the static data structure is that there
is no wastage of memory.

1.4.3 Persistent and Ephimeral Data Structure

The persistent data structures are the data structures which retain their previous
state and modifications can be done by performing certain operations on it.
For example stack can be a persistent data structure in following case
If we push 10, 20, 30 onto it and by performing pop operation we can gain its
previous state. That means -
Thus stack can be a persistent data structure.

30
State 1 : 20 20
10 10 10
stack stack stack
(a) (b) (c)

30
we have pushed 10, 20 and 30 in the
State 2 : 20 stack
10
stack

30 popping the element which is on the top

State 3 : of the stack
20
10
stack

just compare the state 1 (b) and state 4. Both are

same. That means we have gained the previous
State 4 : state stack after performing a 'pop' operation
20 (in state 3)
10
stack
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-7 Introduction to Algorithm and Data Structures

The ephemeral data structures are the data structures in which we cannot retain its
previous state.
For example Queues

State 1 : In queues elements are inserted by one end and deleted by other end. Let us
insert 10, 20, 30 in the queue.

10 10 20 10 20 30

queue queue queue

(a) (b) (c)

State 2 : Now if we delete the element, we can delete it only by other end. That means
10 can be deleted. And queue will be -

20 30

Now this state is not matching with any of the previous states. That means we can
not retain the previous state of the data structure even after performing certain
operations. Such a data structure is called ephemeral data structure.

Review Questions

1. Differentiate between linear and non linear data structure with example.
SPPU : May-17, Marks 3

2. Explain static and dynamic data structures with examples SPPU : Dec.-18, Marks 4

3. Write short note on Linear and Non-Linear data structure with example
SPPU : Dec.-19, Marks 4

Part II : Introduction to Algorithms

1.5 Problem Solving SPPU : Dec.-09, 10, May-10, 11, Marks 12

Problem solving is based on the decisions that are taken. Following are the six steps
of problem solving -
1. Identify the problem : Identifying the problem is the first step in solving the
problem. Problem identification is very essential before solving any problem.
2. Understand the problem : Before solving any problem it is important to
understand it. There are three aspects based on which the problem can be
understood.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-8 Introduction to Algorithm and Data Structures

· Knowledgebase : While solving the problem the knowledgebase can be related

to a person or a machine. If the problem is to be solved for the person then it
is necessary to know what the person knows. If the problem is to be solved for
the machine then its instruction set must be known. Along with this the
problem solver can make use of his/her own instruction set.
· Subject : Before solving the problem the subject on which the problem is based
must be known. For instance : To solve the problem involving Laplace, it is
necessary to know about the Laplace transform.
· Communication : For understanding the problem, the developer must
communicate with the client.
3. Identify the alternative ways to solve the problem : The alternative way to solve
the problem must be known to the developer. These alternatives can be decided by
communicating with the customer.
4. Select the best way to solve the problem from list of alternative solutions : For
selecting the best way to solve the problem, the merits and demerits of each
problem must be analysed. The criteria to evaluate each problem must be
predefined.
5. List the instructions using the selected solution : Based on the
knowledgebase(created/used in step 2) the step by step instructions are listed out.
Each and every instruction must be understood by the person or the machine
involved in the problem solving process.
6. Evaluate the solution : When the solution is evaluated then - i) check whether the
solution is correct or not ii) check whether it satisfies the requirements of the
customer or not.
Example 1.5.1 An admission charge for the cinemax theatre varies according to the age of the
person. Complete the six problem solving steps to calculate the ticket charge given the age of
the person. The charges are as follows :
i) Over 55 : ` 50.00 ii) 21-54 : ` 75.00
iii) 13-20 : ` 50.00 iv) 3-12 : ` 25.00 v) Under 3 : free
(Hint: No need to draw flowchart) SPPU : Dec.-09, Marks 12
Solution : Step 1 : Identify the problem : What are the charges for the person for the
cine ticket?

Step 2 : Understand the problem : Here the age of the person must be known so that
the charge for the ticket can be calculated.

Step 3 : Identify alternatives : No alternative is possible for this problem.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1-9 Introduction to Algorithm and Data Structures

Step 4 : Select the best way to solve the problem : The only way to solve this problem
is to calculate ticket charge based on the age of the person.

Step 5 : Prepare the list of selected solutions :

i. Enter the age of the person.
ii. If age>55 charge for the ticket is ` 50.00
iii. If age>=21 and <=54 charge for the ticket is ` 75.00
iv. If age>=13 and <=20 charge for the ticket is ` 50.00
v. If age>=3 and <=12 charge for the ticket is ` 25.00
vi. If age <=3 charge for the ticket is ` 00.00
vii. Print charge
Step 6 : Evaluate Solution : The charge for the ticket should be according to the age of
the person.

Review Questions

1. State a reason why each of the six problem solving steps is important in developing the best
solution for a problem. Give one reason for each step. SPPU : May-10, Marks 8

2. Consider any one problem and solve that problem using six steps of problem solving. Explain
each step in detail. SPPU : Dec.-10, Marks 8

3. Describe the six steps in problem solving with example. SPPU : May-11, Marks 8

1.6 Difficulties in Problem Solving SPPU : Dec.-10, May-16, Marks 4

Various difficulties in solving the problem are -

· People do not know how to solve particular problem.
· Many times people get afraid of taking decisions
· While following the problem solving steps people complete one or two steps
inadequately.
· People do not define the problem statements correctly.
· They do not generate the sufficient list of alternatives. Sometimes good
alternatives might get eliminated. Sometimes the merits and demerits of the
alternatives is defined hastily.
· The sequence of solution is not defined logically, or the focus of the design is
sometimes on detailed work before the framework solution.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 10 Introduction to Algorithm and Data Structures

· When solving the problems on computer then writing the instructions for the
computer is most crucial task. With lack of knowledgebase one can not write the
proper instruction set for the computers.

Review Questions

1. State and explain any four difficulties with problem solving SPPU : Dec.-10, Marks 4

2. What are the difficulties in problem solving ? Explain any four steps in problem solving with
suitable example. SPPU : May-16, Marks 4

1.7 Introduction to Algorithm SPPU : Dec.-16, May-18, 19, Marks 4

Definition of Algorithm : An algorithm is a finite set of instructions for performing a

particular task. The instructions are nothing but the statements in simple English
language.

Example : Let us take a very simple example of an algorithm which adds the two
numbers and store the result in a third variable.
Step 1 : Start.
Step 2 : Read the first number is variable 'a'
Step 3 : Read the second number in variable 'b'
Step 4 : Perform the addition of both the numbers i.e. and store the result in variable 'c'.
Step 5 : Print the value of 'c' as a result of addition.
Step 6 : Stop.

1.7.1 Characteristics of Algorithm

1. Each algorithm is supplied with zero or more inputs.

2. Each algorithm must produce at least one output
3. Each algorithm should have definiteness i.e. each instruction must be clear and
unambiguous.
4. Each algorithm should have finiteness i.e. if we trace out the instructions of an
algorithm, then for all cases the algorithm will terminate after finite number of
steps.
Each algorithm should have effectiveness i.e. every instruction must be sufficiently
basic that it can in principal be carried out by a person using only pencil and paper.
Moreover each instruction of an algorithm must also be feasible.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 11 Introduction to Algorithm and Data Structures

Review Questions

1. Define algorithm and its characteristics. SPPU : Dec.-16, Marks 4, May-19, Marks 2

2. Define and explain following terms – (i) Data (ii) Data structure (iii) Algorithm.
SPPU : May-18, Marks 3

1.8 Algorithm Design Tools

There are various ways by which we can specify an algorithm.
Pseudo code

Algorithm

Flow chart

Let us discuss these techniques

1.8.1 Pseudocode SPPU : May-10, 11, Dec.-10, Marks 8

· Definition : Pseudo code is nothing but an informal way of writing a program. It

is a combination of algorithm written in simple English and some programming
language.
· In pseudo code, there is no restriction of following the syntax of the programming
language.
· Pseudo codes cannot be compiled. It is Algorithm heading
It consists of name of algorithm, problem
just a previous step of developing a description, input and output
code for given algorithm.
· Even sometimes by examining the
pseudo code one can decide which Algorithm body
It consists of logical body of the algorithm
language has to select for by making use of various programming
implementation. constructs and assignment statement.
The algorithm is broadly divided into two
sections. (Refer Fig. 1.8.1) Fig. 1.8.1 Structure of algorithm
Let us understand some rules for writing
the algorithm.
1. Algorithm is a procedure consisting of heading and body. The heading consists of
keyword Algorithm and name of the algorithm and parameter list. The syntax is

Algorithm name (p1,p2,....................,pn)

This keyword should Here write Write

be written first the name of parameters
an algorithm (if any)

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 12 Introduction to Algorithm and Data Structures

2. Then in the heading section we should write following things :

//Problem Description :
//Input :
//Output :
3. Then body of an algorithm is written, in which various programming constructs
like if, for, while or some assignment statements may be written.
4. The compound statements should be enclosed within { and } brackets.
5. Single line comments are written using // as beginning of comment.
6. The identifier should begin by letter and not by digit. An identifier can be a
combination of alphanumeric string.
It is not necessary to write data types explicitly for identifiers. It will be
represented by the context itself. Basic data types used are integer, float, char,
Boolean and so on. The pointer type is also used to point memory location. The
compound data type such as structure or record can also be used.
7. Using assignment operator ¬ an assignment statement can be given.
For instance :
Variable ¬ expression
8. There are other types of operators such as Boolean operators such as true or false.
Logical operators such as and, or, not. And relational operators such as <, <=, >,
>=, =, ¹
9. The array indices are stored with in square brackets '[' ']'. The index of array
usually start at zero. The multidimensional arrays can also be used in algorithm.
10. The inputting and outputting can be done using read and write.
For example :
write(“This message will be displayed on console”);
read(val);
11. The conditional statements such as if-then or if-then-else are written in
following form :
if (condition) then statement
if (condition) then statement else statement
If the if-then statement is of compound type then { and } should be used for
enclosing block.
12. while statement can be written as :
while (condition) do
{
statement 1
statement 2

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 13 Introduction to Algorithm and Data Structures

:
:
statement n
}
While the condition is true the block enclosed with { } gets executed otherwise
statement after } will be executed.
13. The general form for writing for loop is :
for variable ¬ value1 to valuen do
{
statement 1
statement 2
:
:
statement n
}
Here value1 is initialization condition and valuen is a terminating condition.
Sometime a keyword step is used to denote increament or decreament the value of
variable for example

for i¬1 to n step 1 Here variable i is

{ incremented by 1
Write (i) at each iteration
}
14. The repeat - until statement can be written as :
repeat
statement 1
statement 2
:
:
statement n
until (condition)
15. The break statement is used to exit from inner loop. The return statement is used
to return control from one point to another. Generally used while exiting from
function.
Note that statements in an algorithm executes in sequential order i.e. in the same
order as they appear-one after the other.
A sub-algorithm is complete and independently defined algorithmic module. This
module is actually called by some main algorithm or some another sub-algorithm.
There are two types of sub-algorithms -
1. Function sub-algorithm 2. Procedure sub-algorithm

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 14 Introduction to Algorithm and Data Structures

Example of function sub-algorithm

Function sum(a,b:integer):integer
{
//body of function
//return statement
}

Example of Procedure sub-algorithm

Procedure sum(a,b:integer):integer
{
//body of procedure
}
The difference between function sub-algorithm and procedure sub-algorithm is that,
the function can return only one value where as the procedure can return more than one
value.

Examples of Pseudo Code

Example 1.8.1 Write an pseudo code to count the sum of n numbers.

Solution :

Algorithm sum (1, n)

//Problem Description: This algorithm is for finding the
//sum of given n numbers
//Input: 1 to n numbers
//Output: The sum of n numbers
result ¬ 0
for i ¬ 1 to n do i ¬ i+1
result ¬ result+i
return result
Example 1.8.2 Write a pseudo code to check whether given number is even or odd.

Solution :

Algorithm eventest (val)

//Problem Description: This algorithm test whether given
//number is even or odd
//Input: the number to be tested i.e. val
//Output: Appropriate messages indicating even or oddness
if (val%2=0) then
write (“Given number is even”)
else
write(“Given number is odd”)

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 15 Introduction to Algorithm and Data Structures

Example 1.8.3 Write a pseudo code for sorting the elements.

Solution :

Algorithm sort (a,n)

//Problem Description: sorting the elements in ascending order
//Input:An array a in which the elements are stored and n
//is total number of elements in the array
//Output: The sorted array
for i ¬ 1 to n do
for j ¬ i+1 to n – 1 do
{
if(a[i]>a[j]) then
{
temp ¬ a[i]
a[i] ¬ a[j]
a[j] ¬ temp
}
}
write (“List is sorted”)
Example 1.8.4 Write a pseudo code to find factorial of n number. (n!)

Solution :

Algorithm fact (n)

//Problem Description: This algorithm finds the factorial
//of given number n
//Input: The number n of which the factorial is to be
//calculated.
//Output:factorial value of given n number.
if(n ¬ 1) then
return 1
else
return n*fact(n – 1)
Example 1.8.5 Write a pseudo code to perform multiplication of two matrices.

Solution :

Algorithm Mul(A,B,n)
//Problem Description:This algorithm is for computing
//multiplication of two matrices
//Input:The two matrices A,B and order of them as n
//Output:The multiplication result will be in matrix C
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]

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 16 Introduction to Algorithm and Data Structures

1.8.2 Flowchart

· Flowcharts are the graphical representation of the algorithms.

· The algorithms and flowcharts are the final steps in organizing the solutions.
· Using the algorithms and flowcharts the programmers can find out the bugs in the
programming logic and then can go for coding.
· Flowcharts can show errors in the logic and set of data can be easily tested using
flowcharts.
Symbols used in Flowchart

Flow lines are used to indicate the flow of

data. The arrow heads are important for
flowlines. The flowlines are also used to
connect the different blocks in the
flowchart.
Flowline

These are termination symbols. The start of

the flowchart is represented by the name
of the module in the ellipse and the end Start
of the flowchart is represented by the
keywords End or Stop or Exit
End/Stop/Exit

The rectangle indicates the processing. It

includes calculations, opening and closing
files and so on.
Processing

The parallelogram indicates input and

output.

I/O

The diamond indicates the decision. It has

one entrance and two exits. One exit
indicates the true and other indicates the
false.

Decision

The process module has only one entrance

and one exit.

Process Module

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 17 Introduction to Algorithm and Data Structures

This polygon indicates the loop

A indicates the starting of the counter
Counter
S indicates the step by which the counter
A S B
is incremented or decremented.
B indicates the ending value of the counter
Using the counter the number of times the
looping instruction gets executed.

The on-page connector connects the two

different sections on the same page. A
letter is written inside the circle.
The off-page connector connects the two On page connector
different sections on the different pages.
The page numbers are used in off-page
connector.
These two symbols should be used as little
as possible because then the readability of Off page connector
the flowchart may get affected.

Example 1.8.6 What do you mean by flow chart ? Give the meaning of each symbol used in
flowchart. Draw flowchart to compute the sum of elements from a given integer array
SPPU : May-10, Marks 8
Solution : Refer section 1.8.2 for flowchart and symbols used in it.

Start

Read array
elements

Sum = 0

i=
1 1 n

Sum = Sum + a[i]

Display Sum

Stop

Fig. 1.8.2
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 18 Introduction to Algorithm and Data Structures

Example 1.8.7 Design and explain an algorithm to find the sum of the digits of an integer
number. SPPU : Dec.-10, Marks 6
Solution :
Read N
Remainder=0
Sum=0
Repeat
Remainder=N mod 10
Sum=Sum+remainder
N=N/10
Until N<0
Display Sum
End
Example 1.8.8 What is a difference between flowchart and algorithm ? Convert the algorithm
for computing factorial of given number into flowchart. SPPU : May-11, Marks 8
Solution : Algorithm is a set of instructions written in natural language or pseudo code
and flowchart is a graphical representation of an algorithm.

Read N
Set i and F to 1
While i<=N
F=F * i
Increase the value of i by 1
Display F
End

Start

Read the
number 'n'

fact = 1

i=
1 1 n

fact = fact i

Print the value

of fact

Stop

Fig. 1.8.3 Flowchart for factorial

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 19 Introduction to Algorithm and Data Structures

1.9 Step Count Method

Definition : The frequency count is a count that denotes how many times particular
statement is executed.
For Example : Consider following code for counting the frequency count
void fun()
{
int a;
a=10; ………………………………………..1
printf("%d",a); ……………………………….1
}
The frequency count of above program is 2.

1.10 Complexity of Algorithm SPPU : Dec.-09, 10, 11, 19, May-12, 13, Marks 8

1.10.1 Space Complexity

The space complexity can be defined as amount of memory required by an
algorithm to run.
To compute the space complexity we use two factors : constant and instance
characteristics. The space requirement S(p) can be given as

S(p) = C + Sp

where C is a constant i.e. fixed part and it denotes the space of inputs and outputs.
This space is an amount of space taken by instruction, variables and identifiers. And Sp
is a space dependent upon instance characteristics. This is a variable part whose space
requirement depends on particular problem instance.
There are two types of components that contribute to the space complexity - Fixed
part and variable part.
The fixed part includes space for

· Instructions · Variables · Array size · Space for constants

The variable part includes space for

· The variables whose size is dependent upon the particular problem instance being
solved. The control statements (such as for, do, while, choice) are used to solve
such instances.
· Recursion stack for handling recursive call.
Consider an example of algorithm to compute the space complexity.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 20 Introduction to Algorithm and Data Structures

Example 1.10.1 Compute the space needed by the following algorithms justify your answer.

Algorithm Sum(a,n)
{
s : = 0.0 ;
For i : = 1 to n do
s : = s + a[i] ;
return s
}
In the given code we require space for
s:=0 ¬ O(1)
For i : = 1 to n ¬ O(n)
s : = s + a[i] ; ¬ O(n)
returns ; ¬ O(1)
Hence the space complexity of given algorithm can be denoted in terms of big-oh
notation. It is O(n). We will discuss big oh notation concept in section 1.11.

1.10.2 Time Complexity

The amount of time required by an algorithm to execute is called the time
complexity of that algorithm.
For determining the time complexity of particular algorithm following steps are
carried out -
1. Identify the basic operation of the algorithm
2. Obtain the frequency count for this basic operation.
3. Consider the order of magnitude of the frequency count and express it in terms of
big oh notation.
Example 1.10.2 Write an algorithm to find smallest element in a array of integers and
analyze its time complexity SPPU : May-13, Marks 8
Solution :
Algorithm MinValue(int a[n])
{
min_element=a[0];
for(i=0;i<n;i++)
{
if (a[i]<min_element) then
min_element=a[i];
}
Write(min_element);
}

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 21 Introduction to Algorithm and Data Structures

We will first obtain the frequency Statement Frequency Count

count for the above code
min_element=a[0] 1
By neglecting the constant terms and
by considering the order of magnitude for(i=0;i<n;i++) n+1
we can express the frequency count in
if (a[i]<min_element) n
terms of Omega notation as O(n). Hence then
the frequency count of above code is
Write(min_element); 1
O(n).
Total 2n+3
Review Questions

1. What is space complexity of an algorithm? Explain its importance with example.

SPPU : Dec.-10, Marks 4

2. What do you mean by frequency count and its importance in analysis of an algorithm
SPPU : Dec.-09,10, May-12,13, Marks 6

3. What is time complexity? How is time complexity of an algorithm computed ?

SPPU : Dec.-11, Marks 6

4. What is complexity of algorithm ? Explain with an example. SPPU : Dec.-19, Marks 3

1.11 Asymptotic Notations

SPPU : Dec.-09, 10, 11, 16, 17, 19, May-10, 12, 13, 18, 19, Marks 8

To choose the best algorithm, we need to check efficiency of each algorithm. The
efficiency can be measured by computing time complexity of each algorithm. Asymptotic
notation is a shorthand way to represent the time complexity.
Using asymptotic notations we can give time complexity as “fastest possible”,
“slowest possible” or “average time”.
Various notations such as W, Q and O used are called asymptotic notations.

1.11.1 Big oh Notation

The Big oh notation is denoted by 'O'. It is a method of representing the upper
bound of algorithm's running time. Using big oh notation we can give longest amount
of time taken by the algorithm to complete.
Definition
Let f(n) and g(n) be two non-negative functions.
Let n 0 and constant c are two integers such that n 0 denotes some value of input
and n > n 0 . Similarly c is some constant such that c > 0. We can write

f(n) £ c*g(n)

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 22 Introduction to Algorithm and Data Structures

then f(n) is big oh of g(n). It is also denoted as f(n) Î O (g(n)). In other words f(n) is
less than g(n) if g(n) is multiple of some constant c.

c * g(n)

f(n)

n0 n

f(n) Î O(g(n))
Fig. 1.11.1 Big oh notation

Example : Consider function f(n) = 2n + 2 and g(n) = n 2 . Then we have to find

some constant c, so that f(n) £ c * g(n). As F(n) = 2n + 2 and g(n) = n 2 then we find c
for n = 1 then
f(n) = 2n+ 2
= 2(1) + 2
f(n) = 4
and g(n) = n 2

= (1) 2

g(n) = 1
i.e. f(n) > g(n)
If n = 2 then,
f(n) = 2(2) + 2
= 6
g(n) = ( 2) 2

g(n) = 4
i.e. f(n) > g(n)
If n = 3 then,
f(n) = 2(3) + 2
= 8
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 23 Introduction to Algorithm and Data Structures

g(n) = ( 3) 2

g(n) = 9
i.e. f(n) < g(n) is true.
Hence we can conclude that for n > 2, we obtain
f(n) < g(n)

Thus always upper bound of existing time is obtained by big oh notation.

1.11.2 Omega Notation

Omega notation is denoted by ' W'. This notation is used to represent the lower
bound of algorithm's running time. Using omega notation we can denote shortest
amount of time taken by algorithm.

Definition
A function f(n) is said to f(n)
be in W (g(n)) if f(n) is
bounded below by some c * g(n)
positive constant multiple of
g(n) such that
f(n) ³ c * g(n)
For all n ³ n 0

It is denoted as f(n) Î W
(g(n)). Following graph n0 n
illustrates the curve for W
notation. Fig. 1.11.2 Omega notation f(n) Î W (g(n))

Example :
Consider f(n) = 2n 2 + 5 and g(n) = 7n

Then if n = 0
f(n) = 2 ( 0) 2 + 5

= 5
g(n) = 7 (0)
= 0 i.e. f(n) > g(n)
But if n = 1
f(n) = 2 (1) 2 + 5

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 24 Introduction to Algorithm and Data Structures

= 7
g(n) = 7(1)
7 i.e. f(n) = g(n)
If n = 3 then,
f(n) = 2 ( 3) 2 + 5

= 18 + 5
= 23
g(n) = 7(3)
= 21
i.e. f(n) > g(n)

Thus for n > 3 we get f(n) > c * g(n).

It can be represented as

2n 2 + 5 Î W (n)

Similarly any
n 3 Î W (n) 2

1.11.3 Q Notation
The theta notation is denoted by Q. By this method the running time is between
upper bound and lower bound.

Definition
Let f(n) and g(n) be two
c2 * g(n)
non negative functions. There f(n)
are two positive constants
namely c 1 and c 2 such that
c1 * g(n)
c 1 £ g(n) £ c 2 g(n)

Then we can say that

f(n) Î Q (g(n))
Example :
If f(n) = 2n + 8 and g(n) = 7n. n0 n

where n ³ 2
Fig. 1.11.3 Theta notation f(n) Î Q (g(n))
Similarly f(n) = 2n + 8
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 25 Introduction to Algorithm and Data Structures

g(n) = 7n
i.e. 5n < 2n + 8 < 7n For n ³ 2
Here c1 = 5 and c 2 = 7 with n 0 = 2.
The theta notation is more precise with both big oh and omega notation.

Some Examples of Asymptotic Order

1) log 2 n is f(n) then
log 2 n Î O(n) Q log 2 n £ O(n), the order of growth of log 2 n is
slower than n.
log 2 n Î O(n 2 ) Q log 2 n £ O(n 2 ), the order of growth of log 2 n

is slower than n 2 as well.

But
log 2 n Ï W(n) Q log 2 n £ W(n) and if a certain function F(n) is
belonging to W(n) it should satisfy the
condition F(n) ³ c * g(n)
Similarly log 2 n Ï W(n 2 ) or W (n 3 )
2) Let f(n) = n(n – 1)/2
Then
n 2 -1
n(n – 1)/2 Ï O(n) Q f(n) > O(n) we get f(n) = n(n – 1)/2 =
2
i.e. maximum order is n 2 which is > O(n).
Hence F(n) Ï O(n)
But n(n – 1)/2 Î O (n ) 2 As f(n) £ O (n 2 )

and n(n – 1)/2 Î O (n 3 )

Similarly,
n(n – 1)/2 Î W (n) Q f(n) ³ W (n)
n(n – 1)/2 Î W (n ) 2 Q f(n) ³ W (n 2 )

n(n – 1)/2 Ï W (n 3 ) Q f(n) > W (n 3 )

1.11.4 Properties of Order of Growth

1. If f1 (n) is order of g 1 (n) and f2 (n) is order of g 2 (n) ,

then f1 (n) + f2 (n) Î O(max(g 1 (n), g 2 (n)) .

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 26 Introduction to Algorithm and Data Structures

2. Polynomials of degree m Î Q (n m ) .

That means maximum degree is considered from the polynomial.

For example : a 1 n 3 + a 2 n 2 + a 3 n + c has the order of growth Q (n 3 ) .

3. O(1) < O(log n) < O(n) < O(n 2 ) < O(2 n ) .

4. Exponential functions a n have different orders of growth for different values of a.

Key Points
i) O(g(n)) is a class of functions F(n) that grows less fast than g(n), that means F(n) possess
the time complexity which is always lesser than the time complexities that g(n) have.
ii) Q (g(n)) is a class of functions F(n) that grows at same rate as g(n).
iii) W(g(n)) is a class of functions F(n) that grows faster than or atleast as fast as g(n). That
means F(n) is greater than W(g(n).

Example 1.11.1 Analyze time complexity of the following code segments :

i) for (i = 1 ; i <= n ; i++) ii) i = 1
for (j = 1 ; j <= m ; j++) while (i <= n)
for (k = 1 ; k <= p ; k++) { x++ ;
x=x+1; i++;
}
iii) int process (int no)
{
if (no <= 0)
return (0) ;
else
return (no + process (no – 1));
}
SPPU : Dec.-10, Marks 8
3
Solution : i) O(n ) ii) O(n) iii) O(n)

1.11.5 How to Choose the Best Algorithm ?

If we have two algorithms that
n log 2 n n log 2 n n2 n3 2n
perform same task and the first one
has a computing time of O ( n) and the 1 0 0 1 1 2

( )
second of O n 2 , then we will usually 2 1 2 4 8 4
prefer the first one. 4 2 8 16 64 16
The reason for this is that as n 8 3 24 64 512 256
increases the time required for the
16 4 64 256 4096 65536
execution of second algorithm will get
far more than the time required for 32 5 160 1024 32768 2147483648
the execution of first.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 27 Introduction to Algorithm and Data Structures

We will study various values for computing function for the constant values. The
graph given below will indicate the rate of growth of common computing time
functions.
Notice how the times O ( n) and O (n log n) grow much more slowly than the others.
For large data sets algorithms with a complexity greater than O (n log n) are often
impractical. The very slow algorithm will be the one having time complexity 2n .

n
2 3
65536 n

32768

16384
2
n
8192

4096

2048

1024
n log2 n
512

256
n
128

64

32

16 log2 n

1 2 4 8 16 32 64 128

Fig. 1.11.4 Rate of growth of common computing time function

Review Questions

1. Explain different asymptotic notation

SPPU : Dec.-09, May-12, Marks 4, May-13, Marks 6

2. With respect to algorithm analysis, explain the following terms :

i) Omega notation ii) Theta notation iii) Big oh notation
SPPU : May-10, Dec.-11, Marks 6

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 28 Introduction to Algorithm and Data Structures

3. Explain asymptotic notations Big O, Theta and Omega with one example each.
SPPU : Dec.-16, 17, May-18, Marks 6, Dec.-19, Marks 3

4. What is complexity analysis of an algorithm ? Explain the notations used in complexity

analysis. SPPU : May-19, Marks 6

1.12 Analysis of Programming Constructs

SPPU : May-10, 13, 14, Dec.-11, 13, Marks 8

Example 1.12.1 Obtain the frequency count for the following code

Solution :
void fun()
{
int a;
a=0; ………………………………………….1
for(i=0;i<n;i++) …………………………….n+1
{
a = a+i; …………………………………n
}
printf("%d",a); ……………………………….1
}
The frequency count of above code is 2n+3
The for loop in above given fragment of code is executed n times when the condition
is true and one more time when the condition becomes false. Hence for the for loop the
frequency count is n+1. The statement inside the for loop will be executed only when
the condition inside the for loop is true. Therefore this statement will be executed for n
times. The last printf statement will be executed for once.
Example 1.12.2 Obtain the frequency count for the following code

Solution :
void fun(int a[][],int b[][])
{
int c[3][3];
for(i=0;i<m;i++) .....................................m+1
{
for(j=0;j<n;j++) ...................................m(n+1)
{
c[i][j]=a[i][j]+b[i][j]; ...........................m.n
}
}
The frequency count =(m+1)+m(n+1)+mn=2m+2mn+1=2m(1+n)+1

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 29 Introduction to Algorithm and Data Structures

Example 1.12.3 Obtain the frequency count for the following code
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
} SPPU : May-13, Marks 8; Dec.-13, Marks 3
Solution : After counting the frequency
count, the constant terms can be Statement Frequency Count
neglected and only the order of
for(i=1;i<=n;i++) n+1
magnitude is considered. The time
complexity is denoted in terms of for(j=1;j<=n;j++) n.(n+1)
algorithmic notations. The Big oh
c[i][j]=0; n.(n)
notation is a most commonly used
algorithmic notation. For the above for(k=1;k<=n;k++) n.n(n+1)
frequency count all the constant terms c[i][j]=c[i][j]+a[i][k]*b[k][j n.n.n
are neglected and only the order of ];
magnitude of the polynomial is 3 2
Total 2n +3n +2n+1
considered. Hence the time complexity
for the above code can be O(n3). The
higher order is the polynomial is always considered.
Example 1.12.4 Obtain the frequency count for the following code i=1;
do
{
a++;
if(i==5)
break;
i++;
}while(i<=n)

Solution :
Statement Frequency Count
i=1; 1
a++; 5
if(i==5) 5
break; 1
i++; 5
while(i<=n) 5
Total 22

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 30 Introduction to Algorithm and Data Structures

Example 1.12.5 Obtain the frequency count for the following code
m=n/2;
for(i=0;i+m<m;i++)
{
a++;
k++;
}
Solution :

Statement Frequency Count

m=n/2 1
for(i=0;i+m<m;i++) (n/2)+1
a++; n/2
k++; n/2
Total (3n/2)+2

If we consider only the degree of the polynomial for this code then the time
complexity in terms of Big-oh notation can be specified as O(n/2).
Example 1.12.6 Find the frequency count (F.C.) of the given code :
Explain each step.
double IterPow(double X, int N)
{
double Result = 1;
while (N > 0)
{
Result = Result *X;
N--;
}
return Result;
} SPPU : May-10, Marks 6

Solution :

Statement Frequency Count

double Result=1 1
while(N>0) N+1
Result=Result*X N
N-- N
return Result 1
Total 3N+3

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 31 Introduction to Algorithm and Data Structures

Example 1.12.7 What is frequency count of a statement ? Analyze time complexity of the
following code :
i) for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
for(k = 1; k <= p; k++)
sum = sum + i;
ii) i = n;
while(i ³ 1)
{i– –;} SPPU : Dec.-11, Marks 6, May-14, Marks 3
Solution : i) ii)

Statement Frequency Count Statement Frequency Count

for(i=1;i<=n;i++) n+1
i=n 1
for(j=1;j<=m;j++) n(m+1)
while(i>=1) n+1
for(k=1;k<=p;k++) n.m.(p+1)
i– – n
sum=sum+i n.m.p
Total 2(n+1)
Total 2(n+nm+nmp)+1

Example 1.12.8 Determine the frequency counts for all the statements in the following
program segment
i=10;
for(i=10;i<=n;i++)
for(j=1;j<i;j++)
x=x+1; SPPU : May-13, Marks 6
Solution : Assume (n–10+2)=m.
Then the total frequency count is - Statement Frequency Count
The outer loop will execute for i=10; 1
m times. The inner loop is
for(i=10;i<=n;i++) m (we assume the count of
dependant upon the outer loop.
execution is m)
Hence it will be (m+1)/2. Hence
overall frequency count is for(j=1;j<i;j++) m((m+1)/2)
(1+m+m )(m(m+1)/2)
2
x=x+1; m(m)
If we consider only the order of
magnitude of this code then overall time complexity in terms of big oh notation is O(n2).
If an algorithm takes time O(logn) then it is faster than any other algorithm, for
larger value of n. Similarly O(nlogn) is better than O(n2). Various computing time can be
O(1), O(logn), O(n),O(nlogn), O(n2), O(n3) and O(2n).

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 32 Introduction to Algorithm and Data Structures

1.13 Recurrence Relation SPPU : Dec.-18, Marks 2

· Definition :
The recurrence equation is an equation that defines a sequences resursively. It is
normally in following form :

T(n) = T(n – 1) + n for n > 0 (1)

Recurrence relation
T(0) = 0 (2)

Initial condition

· The recurrence equation can have infinite number of sequence.

· The general solution to the recursive function specifies some formula.
· For example : consider a recurrence relation
T(n) = 2T (n – 1) + 1 for n > 1
T(1) = 1

By solving this relation we will get T(n) = 2 n – 1 where n > 1.

Review Question

1. What is recurrence relation ? Explain with example. SPPU : Dec.-18, Marks 2

1.14 Solving Recurrence Relation

The recurrence relation can be solved by following methods -
1. Substitution method 2. Master's method.
Let us discuss methods with suitable examples -

1.14.1 Substitution Method

The substitution method is a kind of method in which a guess for the solution is
made
There are two types of substitutions -

· Forward substitution · Backward substitution

Forward Substitution Method - This method makes use of an initial condition in the
initial term and value for the next term is generated. This process is continued until some
formula is guessed. Thus in this kind of substitution method, we use recurrence equations
to generate the few terms.
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 33 Introduction to Algorithm and Data Structures

For example -
Consider a recurrence relation
T(n) = T(n – 1) + n

With initial condition T(0) = 0.

Let,
T(n) = T(n – 1) + n … (1.14.1)

If n = 1 then
T(1) = T(0) + 1
= 0+1 Q Initial condition
\ T(1) = 1 … (1.14.2)

If n = 2, then
T(2) = T(1) + 2
= 1+2 Q equation (1.14.2)
\ T(2) = 3 … (1.14.3)

If n = 3 then
T(3) = T(2) + 3
= 3+3 Q equation (1.14.4)
\ T(3) = 6 … (1.14.5)

By observing above generated equations we can derive a formula

n(n + 1) n2 n
T(n) = = +
2 2 2

We can also denote T(n) in terms of big oh notation as follows -

T(n) = O (n 2 )

But, in practice, it is difficult to guess the pattern from forward substitution. Hence
this method is not very often used.

Backward Substitution : In this method backward values are substituted recursively in

order to derive some formula.
For example - Consider, a recurrence relation
T(n) = T(n – 1) + n … (1.14.6)

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 34 Introduction to Algorithm and Data Structures

With initial condition T(0) = 0

T(n – 1) = T (n – 1 – 1) + (n – 1) … (1.14.7)

Putting equation (1.14.7) in equation (1.14.6) we get

T(n) = T(n – 2) + (n – 1) + n … (1.14.8)

Let
T(n – 2) = T (n – 2 – 1) + (n – 2) … (1.14.9)
Putting equation (1.14.9) in equation (1.14.8) we get.
T(n) = T(n – 3) + (n – 2) + (n – 1) + n
M
= T(n – k) + (n – k + 1) + (n – k + 2) + … + n

if k = n then
T(n) = T(0) + 1 + 2 + … n
T(n) = 0 + 1 + 2 + … + n Q T(0) = 0
n(n + 1) n2 n
T(n) = = +
2 2 2

Again we can denote T(n) in terms of big oh notation as

T(n) Î O (n 2 )
Example 1.14.1 Solve the following recurrence relation T(n) = T(n – 1) + 1 with T(0) = 0 as
initial condition. Also find big oh notation.
Solution : Let,

T(n) = T(n – 1) + 1

By backward substitution,
T(n – 1) = T(n – 2) + 1
\ T(n) = T ( n – 1) + 1
= (T(n – 2) + 1) + 1
T(n) = T(n – 2) + 2
Again T(n – 2) = T(n – 2 – 1) + 1
= T(n – 3) + 1
\ T(n) = T(n – 2) + 2
= (T(n – 3) + 1) + 2
®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 35 Introduction to Algorithm and Data Structures

T(n) = T(n – 3) + 3
M
T(n) = T(n – k) + k … (1)

If k = n then equation (1) becomes

T(n) = T(0) + n
= 0+n Q T(0) = 0
T(n) = n

\ We can denote T(n) in terms of big oh notation as

T(n) = O(n)
Example 1.14.2 Solve the following recurrence :
T(1) = 1
T(n) = 4T (n/3) + n 2 for x ³ 2
Solution :
2
n n n n
T(n) = 4T æç ö÷ + n 2 T æç ö÷ = 4T æç ö÷ + æç ö÷
è 3ø è 3ø è 9ø è 3ø

é æ n ö n2 ù
= 4 ê4 × T ç ÷ + + n2
è 2ø 2ú
ë 3 3 û

æ n ö n2
= 4 2T ç ÷ + 4 × + n2
è 32 ø 32

æ n ö 13n 2
= 4 2T ç ÷ +
è 32 ø 32
2
n 13n 2 n n n
= 16 × T æç ö÷ + Q T æç ö÷ = 4T æç ö÷ + æç ö÷
è 9ø 9 è 9ø è 27 ø è 9 ø

é n n 2 ù 13n 2 n n n2
= 16 ê 4 × T æç ö÷ + + Q T æç ö÷ = 4T æç ö÷ +
è 27 ø 81 ú 9 è 9ø è 27 ø 81
ë û

n n 2 13n 2
= 64T æç ö÷ + 16 × +
è 27 ø 81 9

n 133n 2
= 64T æç ö÷ +
è 27 ø 81

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 36 Introduction to Algorithm and Data Structures

2
æ n ö æ n ö
= 4 3T ç ÷ + 133 ×ç ÷
è 33 ø è 32 ø

M
2
æ n ö æ n ö
= 4 kT ç ÷ + C ç k- 1 ÷ Q 133 + C 1 = C
è 3k ø è3 ø

n
Now if we assume = 1 then n = 3 k and k = log 3 n
3k
2
æ n ö n
= 4 k T(1) + C ç ÷ Q = 1
è 3k - 1 ø 3k

Purposely we kept constant term in terms of n.

C
= 4 k ×1 + ×n2 Q T(1) = 1
(3 1 ) 2
k -

C
= 4 k + C1 × n 2 Q C1 =
k- 1 2
(3 )

= 4 log 3 n + C 1 n 2

= n log 3 4 + C 1 n 2 Q a log b n = n log b a

= n 1.26 + C × n 2

T(n) » Q (n 2 )

Example 1.14.3 Solve the following recurrence relations -

n n
i) T(n) = 2T æç ö÷ + C T(1) = 1 ii) T(n) = T æç ö÷ + C T(1) = 1
è 2ø è 3ø
Solution : i) Let

n
T(n) = 2T æç ö÷ + C
è 2ø

æ n ö
= 2 ç 2T æç ö÷ + C÷ + C
è è 4 ø ø

n
= 4T æç ö÷ + 3C
è4ø

æ n ö
= 4 ç 2T æç ö÷ + C÷ + 3C
è è 8ø ø

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 37 Introduction to Algorithm and Data Structures

n
= 8T æç ö÷ + 7C
è 8ø

æ n ö
= 2 3Tç 3
÷ + (2 - 1) C
èn3ø

M
æ n ö
T(n) = 2 k T ç ÷ + (2 k - 1) C
è 2k ø

If we 2 k = n then
n
T(n) = nT æç ö÷ + (n - 1) C
è nø

= nT(1) + (n – 1) C
T(n) = n + (n – 1) C Q T(1) = 1

ii) Let,
n
T(n) = T æç ö÷ + C
è 3ø

æ n ö
= ç T æç ö÷ + C÷ + C
è è 9ø ø

n
= T æç ö÷ + 2C
è 9ø

é n ù
= êT æç ö÷ + Cú + 2C
ë è 27 ø û
n
= T æç ö÷ + 3C
è 27 ø

M
æ n ö
= T ç ÷ + kC
è 3k ø

If we put 3 k = n then
n
= T æç ö÷ + log 3 n × C
è nø

= T (1) + log 3 n × C
T(n) = C × log 3 n + 1 Q T(1) = 1

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 38 Introduction to Algorithm and Data Structures

Example 1.14.4 Solve the recurrence relation by iteration :

T(n) = T ( n - 1) + n 4 .

Solution : Let

T(n) = T(n – 1) + n 4

By backward substitution method,

T(n) = [T (n - 2) + (n - 1) 4 ] + n 4 Q T(n - 1) = T(n - 2) + (n - 1) 4

= T(n - 2) + (n - 1) 4 + n 4

= [T(n - 3) + (n - 2) 4 ] + (n - 1) 4 + n 4

= T(n - 3) + (n - 2) 4 + (n - 1) 4 + n 4

= [T(n - 4) + (n - 3) 4 ] + (n - 2) 4 + (n - 1) 4 + n 4

= T(n - 4) + (n - 3) 4 + (n - 2) 4 + (n - 1) 4 + n 4

= T(n - k) + (n - k + 1) 4 + (n - k + 2) 4 + (n - k + 3) 4 + K n 4

If k = n then

= T(n - n) + (n - n + 1) 4 (n - n + 2) 4 + (n - n + 3) 4 + L + n 4

= T(0) + 1 4 + 2 4 + 3 4 + K + n 4

n
= T(0) + å n4
i= 1

n n
= T(0) + n(n 4 ) Q å n4 = n4 × å 1 = n4 ×n
i= 1 i= 1

= 0 + n5 Q Assume T(0) = 0 as initial condition

\ T(n) » q(n 5 )

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 39 Introduction to Algorithm and Data Structures

Example 1.14.5 Consider the following code :

int sum (int a [ ], n)
{
count = count + 1 ;
if (n < = 0)
{
count = count + 1 ;
return 0 ;
}
else
{
count = count + 1
return sum (a, n – 1)+a[n] ;
}
}
Write the recursive formula for the above code and solve this recurrence relation.

Solution : In the above code the following statement gets executed at least twice

count = count + 1

In the else part, there is a recursive call to the function sum, by changing the value
of n by n – 1, each time.
Hence the recursive formula for above code will be

T(n) = T(n – 1) + 2

For count
For recursive
statement
call to function
sum in else
part.

T(0) = 2

We can solve this recurrence relation using backward substitution. It will be

= [T(n – 2) + 2] + 2

\ = T (n – 2)+2(2)

= [T(n – 3) + 2]+ 2(2)

\ T(n – 2) = T(n – 3) + 3 × (2)

T(n) = T(n – n) + n × (2)

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 40 Introduction to Algorithm and Data Structures

= T(0) + 2n

= 2+2×n Q T(0) = 2

T(n) = 2(n+1)

We can denote the time complexity in the form of big oh notation as O(n).

1.14.2 Master's Method

We can solve recurrence relation using a formula denoted by Master's method.
T(n) = aT (n b) + F(n) where n ³ d and d is some constant.

Then the Master theorem can be stated for efficiency analysis as -

If F(n) is Q (n d ) where d ³ 0 in the recurrence relation then,

1. T(n) = Q (n d ) if a < b d

2. T(n) = Q (n d log n) if a = b
log ba
3. T(n) = Q (n ) if a > b d

Let us understand the Master theorem with some examples :

Example 1.14.6 Solve the following recurrence relation T(n) = 4T (n/2) + n

Solution : We will map this equation with

T(n) = aT (n/b) + f(n)

Now f(n) is n i.e. n 1 . Hence d = 1.

a = 4 and b = 2 and
a > b d i.e. 4 > 2 1
log ba
\ T(n) = Q (n )
log 2 4
= Q (n )

= Q (n 2 ) Q log 2 4 = 2

Hence time complexity is Q (n 2 ).

For quick and easy calculations of logarithmic values to base 2 following table can
be memorized.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 41 Introduction to Algorithm and Data Structures

m k

1 0

2 1

4 2

8 3

16 4

32 5

64 6

128 7

256 8

512 9

1024 10

Another variation of Master theorem is

For T(n) = aT (n/b) + f(n) if n ³ d

log ba - e
1. If f(n) is O (n ), then
log ba
T(n) = Q (n )
log ba
2. If f(n) is Q (n log k n), then
log ba
T(n) = Q (n log k+ 1 n)
log ba + e
3. If f(n) is W (n ), then

T(n) is = Q (f(n))

Example 1.14.7 Solve the following recurrence relation. T(n) = 2T(n/2) + n log n

Solution :

Here f(n) = n log n

a = 2, b=2
log 2 2 = 1

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 42 Introduction to Algorithm and Data Structures

According to case 2 given in above Master theorem

log 2 2
f(n) = Q (n log 1 n) i.e. k=1
log ba
Then T(n) = Q (n log k+ 1 n)
log 2 2
= Q (n log 2 n)

= Q (n 1 log 2 n)

\ T(n) = Q (n log 2 n)

Example 1.14.8 Solve the following recurrence relation T(n) = 8T (n/2) + n 2

Solution :

Here f(n) = n 2

a = 8 and b = 2
\ log 2 8 = 3

Then according to case 1 of above given Master theorem

log ba - e
f(n) = O ( n )
log 2 8 - e
= O (n )

= O ( n 3 - e ). If we put e = 1 then O (n 3 - 1) = O (n 2 ) = f(n)

log ba
Then T(n) = Q ( n )
log 2 8
\ T(n) = Q ( n )

T(n) = Q (n 3 )

Example 1.14.9 Solve the following recurrence relation T(n) = 9T (n/3) + n 3

Solution :
Here a = 9, b=3 and f(n) = n 3
And log 3 9 = 2

According to case 3 in above Master theorem

log 3 9 + e
As f(n) is = W ( n )

i.e. W ( n 2 + e ) and we have f(n) = n 3 .

Then to have f(n) = W(n). We must put e = 1.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 43 Introduction to Algorithm and Data Structures

Then T(n) = Q (f(n))

Then T(n) = Q (f(n))
T(n) = Q (n 3 )

Example 1.14.10 Solve the following recurrence relation. T(n) = T(n/2) + 1

Solution : Here a = 1 and b = 2.

and log 2 1 = 0

Now we will analyze f(n) which is = 1.

We assume f(n) = 2 k
when k = 0 then f(n) = 2 0 = 1.
That means according to case 2 of above given Master theorem.
log ba
f(n) = Q (n log k n)
log 2 1
= Q (n log 0 n)

= Q (n 0 × 1)

= Q (1) Q n0 = 1
log ba
\ We get T(n) = Q (n log k+ 1 n)
log 2 1
= Q (n log 0+ 1 n)

= Q (n 0 × log 1 n)

T(n) = Q (log n) Q n0 = 1

Example 1.14.11 Find the complexity of the following recurrence relation. T(n) = 9T(n/3) + n

Solution : Let T(n) = 9T (n 3) + n

¯ ¯ ¯
a b f(n)

\ We get a = 9, b = 3 and f(n) = n.

log b a log 3 9
n = n = n2
Now f(n) = n
log b a - e
i.e. T(n) = f(n) = Q (n ) = Q (n 2 - e )

When e = 1. That means case 1 is applicable. According to case 1, the time

complexity of such equations is

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 44 Introduction to Algorithm and Data Structures

log b a
T(n) = Q (n )

= Q (n log 3 9 )

T(n) = Q (n 2 )

Hence the complexity of given recurrence relation is Q(n 2 ).

Example 1.14.12 Solve recurrence relation T(n) = k × T ( n k) + n 2 when T(1) = 1, and k is any
constant.
Solution : Let,

n
T(n) = k × T æç ö÷ + n 2 be a recurrence relation. Let us use substiturion
è kø
method

If we assume k = 2 then the equation becomes

2
n n n n
T(n) = 2T æç ö÷ + n 2 T æç ö÷ = 2T æç ö÷ + æç ö÷
è 2ø è 2ø è 4ø è 2ø

é n n2 ù
= 2 ê 2 × T æç ö÷ + ú+n
2
ë è 4 ø 4 û

n n2
= 4T æç ö÷ + + n2
è4ø 2
2
n 3n 2 n n n
= 4T æç ö÷ + T æç ö÷ = 2T æç ö÷ + æç ö÷
è4ø 2 è4ø è 8ø è 4ø

é n n 2 ù 3n 2
= 4 ê 2 × T æç ö÷ + +
ë è 8 ø 16 úû 2

n n 2 3n 2
= 8T æç ö÷ + +
è 8ø 4 2
2
n 7n
= 8T æç ö÷ +
è 8ø 4

æ n ö 2k - 1 2
= 2kT ç ÷ + n
è 2k ø 2k - 1

æ n ö 2k - 1
= 2 k T ç ÷ + Cn 2 Q = C = Constant
è 2k ø 2 k- 1

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 45 Introduction to Algorithm and Data Structures

n
If we put = 1 then 2 k = n and k = log 2 n
2k
= nT(1) + Cn 2

= n + Cn 2 Q T(1) = 1

T(n) = Q (n) 2

Alternate Method
We can solve the given recurrence relation using Master's theorem also.
n
T(n) = k × T æç ö÷ + n 2
è kø
¯ ¯ ¯
a b f(n)
log b a
By Master's theorem n = n log k k = n 1

For T(n) = f(n) we need

T(n) = n log k k + e Applying case 3

= n1+ 1 when e = 1

= f(n) i. e. n 2

\ T(n) = Q(f(n))

T(n) = Q(n 2 )

1.15 Best, Worst and Average Case Analysis

If an algorithm takes minimum amount of time to run to completion for a specific
set of input then it is called best case time complexity.

For example : While searching a particular element by using sequential search we

get the desired element at first place itself then it is called best case time complexity.

If an algorithm takes maximum amount of time to run to completion for a specific

set of input then it is called worst case time complexity.

For example : While searching an element by using linear searching method if

desired element is placed at the end of the list then we get worst time complexity.
The time complexity that we get for certain set of inputs is as a average same. Then
for corresponding input such a time complexity is called average case time complexity.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 46 Introduction to Algorithm and Data Structures

Consider the following algorithm

Algorithm Seq_search(X[0 … n – 1 ],key)
// Problem Description: This algorithm is for searching the
//key element from an array X[0…n – 1] sequentially.
//Input: An array X[0…n – 1] and search key
//Output: Returns the index of X where key value is present
for i ¬ 0 to n – 1 do
if(X[i]=key)then
return i
Best case time complexity
Best case time complexity is a time complexity when an algorithm runs for short
time. In above searching algorithm the element key is searched from the list of n
elements. If the key element is present at first location in the list(X[0…n–1]) then
algorithm runs for a very short time and thereby we will get the best case time
complexity. We can denote the best case time complexity as
C best = 1

Worst case time complexity

Worst case time complexity is a time complexity when algorithm runs for a longest
time. In above searching algorithm the element key is searched from the list of n
elements. If the key element is present at nth location then clearly the algorithm will run
for longest time and thereby we will get the worst case time complexity. We can denote
the worst case time complexity as
C worst = n

The algorithm guarantees that for any instance of input which is of size n, the
running time will not exceed Cworst(n). Hence the worst case time complexity gives
important information about the efficiency of algorithm.

Average case time complexity

This type of complexity gives information about the behaviour of an algorithm on
specific or random input. Let us understand some terminologies that are required for
computing average case time complexity.
Let the algorithm is for sequential search and
P be a probability of getting successful search.
n is the total number of elements in the list.
The first match of the element will occur at ith location. Hence probability of
occurring first match is P/n for every ith element.
The probability of getting unsuccessful search is (1 – P).

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 47 Introduction to Algorithm and Data Structures

Now, we can find average case time complexity Cavg(n) as -

C avg (n) = Probability of successful search (for elements 1 to n in the list)
+ Probability of unsuccessful search
There may be n elements
P P P
C avg (n) = é1 × + 2 × + ... + i × ù + n × (1 - P) at which chances of 'not
êë n n n úû getting element' are
P possible. Hence n.(1 – P)
= [1 + 2 + ... + i ... n] + n (1 - P)
n

P n (n + 1)
= + n (1 - P)
n 2
P (n + 1)
C avg (n) = + n (1 - P)
2

Thus we can obtain the general formula for computing average case time complexity.
Suppose if P = 0 that means there is no successful search i.e. we have scanned the
entire list of n elements and still we do not found the desired element in the list then in
such a situation,
C avg (n) = 0(n + 1)/2 + n (1 – 0)
C avg (n) = n
Thus the average case running time complexity becomes equal to n.
Suppose if P = 1 i.e. we get a successful search then
C avg (n) = 1 (n + 1)/2 + n (1 – 1)
C avg (n) = (n + 1)/2

That means the algorithm scans about half of the elements from the list.
For calculating average case time complexity we have to consider probability of
getting success of the operation. And any operation in the algorithm is heavily
dependent on input elements. Thus computing average case time complexity is difficult
than computing worst case and best case time complexities.

1.16 Introduction to Algorithm Design Strategies

SPPU : May-17, 18, Dec.-17, 19, Marks 6

Algorithm design strategy is a general approach by which many problems can be

solved algorithmically. These problems may belong to different areas of computing.
Algorithmic strategies are also called as algorithmic techniques or algorithmic
paradigm.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 48 Introduction to Algorithm and Data Structures

· Various algorithm techniques are-

¡ Brute Force : This is a straightforward technique with naive approach.

¡ Divide-and-Conquer : The problem is divided into smaller instances.

¡ Greedy Technique : To solve the problem locally optimal decisions are made.

¡ Backtracking : In this method, we start with one possible move out from many
moves out and if the solution is not possible through the selected move then we
backtrack for another move.

1.16.1 Divide and Conquer

Problem of size n
· In divide and conquer
method, a given problem is,
1) Divided into smaller sub
problems. Sub problem 1 Sub problem 1
of size n/2 of size n/2
2) These sub problems are
solved independently.
3) If necessary, the solutions
Solution to Solution to
of the sub problems are sub problem 1 sub problem 2
combined to get a
solution to the original
problem.
Solution to original
· If the sub problems are problem
large enough, then divide
and conquer is reapplied. Fig. 1.16.1 Divide and conquer technique
The divide and conquer technique is as shown in Fig. 1.16.1.
The generated sub problems are usually of same type as the original problem. Hence
sometimes recursive algorithms are used in divide and conquer strategy.

1.16.1.1 Merge Sort

The merge sort is a sorting algorithm that uses the divide and conquer strategy. In
this method division is dynamically carried out.
Merge sort on an input array with n elements consists of three steps:
Divide : partition array into two sub lists s1 and s2 with n/2 elements each.
Conquer : Then sort sub list s1 and sub list s2.
Combine : merge s1 and s2 into a unique sorted group.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 49 Introduction to Algorithm and Data Structures

Consider the elements as

70, 20, 30, 40, 10, 50, 60
Now we will split this list into two sublists.

70 20 30 40 10 50 60

Divide Divide

70 20 30 40 10 50 60
Divide Divide

70 20 30 40 10 50 60

Divide Divide

70 20 30 40 10 50 60

Merge Merge

20 70 30 10 40 50 60

Merge Merge

20 30 70 10 40 50 60

Merge Merge

10 20 30 40 50 60 70

Fig. 1.16.2

Pseudo Code
Algorithm MergeSort(int A[0…n-1],low,high)
//Problem Description: This algorithm is for sorting the
//elements using merge sort
//Input: Array A of unsorted elements, low as beginning
//pointer of array A and high as end pointer of array A
//Output: Sorted array A[0…n-1]
if(low < high)then
{
mid ¬ low+high)/2 //split the list at mid
MergeSort(A,low,mid) //first sublist
MergeSort(A,mid+1,high) //second sublist
Combine(A,low,mid,high) //merging of two sublists
}
Algorithm Combine(A[0…n-1],low, mid, high)
{
k ¬ low; //k as index for array temp
i ¬ low; //i as index for left sublist of array A

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 50 Introduction to Algorithm and Data Structures

j ¬ mid+1 //j as index for right sublist of array A

while(i <= mid and j <= high)do
{
if(A[i]<=A[j])then
//if smaller element is present in left sublist
{
//copy that smaller element to temp array
temp[k] ¬ A[i]
i ¬ i+1
k ¬ k+1
}
else //smaller element is present in right sublist
{
//copy that smaller element to temp array
temp[k] ¬ A[j]
j ¬ j+1
k ¬ k+1
}
}
//copy remaining elements of left sublist to temp
while(i<=mid)do
{
temp[k] ¬ A[i]
i ¬ i+1
k ¬ k+1
}
//copy remaining elements of right sublist to temp
while(j<=high)do
{
temp[k] ¬ A[j]
j ¬ j+1
k ¬ k+1
}

Logic Explanation
To understand above algorithm consider a list of elements as

70 20 30 40 10 50 60

0 1 2 3 4 5 6

­ ­ ­

low mid high

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 51 Introduction to Algorithm and Data Structures

Then we will first make two sublists as

low high
0 1 2 3 4 5 6
70 20 30 40 10 50 60 Merge sort (A, low, mid)

4
1 This list is further
subdivided This list can be
subdivided
0 1 2 3
70 20 30 40

2 This list is
3 This list
subdivided can be Merge sort (A, mid+1, high)
subdivided

70 20 30 40 10 50 60
This list
7 Combine 5 can be
Combine two
subdivide
As A[j] < A[i] sublists in
copy A[j] to temp array 6 10 50 10
temp Combine two
sublists

20 70 30 40 9 Combine two
sublists
8 Combine
these two 10 50
20 30 40 70 sublists

10 50 60

11 Combine two
sublists
10 20 30 40 50 60 70

Fig. 1.16.3

Let us see the combine operation more closely with the help of some example.
Consider that at some instance we have got two sublits 20, 30, 40, 70 and 10, 50, 60,
then

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 52 Introduction to Algorithm and Data Structures

Array A (left sublist) Array A (right sublist)

Applicable part of
20 30 40 70 10 50 60 Algorithm

i j
if (A[i]<= A[j])
Initially k = 0. Then k will be incremented {
temp[k] A[i]
temp i i+1
10 k k+1
}
0 el else
k get s e p a r t
s ex o {
ecute f a l g o r ith m
d temp[k] A[j]
j j+1
Note that A (left sublist) A (right sublist)
k k+1
i remains }
there and j is 20 30 40 70 10 50 60
incremented
i j

Array A (left sublist) Array A (right sublist)

Applicable part of
20 30 40 70 10 50 60 Algorithm

i j

k = 1. It is advanced later on
if (A[i]<= A[j])
temp {
10 20 temp [k] A[i]
if part of algorithm i i+1
0 1
gets executed k k+1
k
moves ahead }
else
{
Note that Array A (left sublist) Array A (right sublist) temp [k] A[j]
j remains there j j+1
and only i is 20 30 40 70 10 50 60
k k+1
incremented
}
i j

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 53 Introduction to Algorithm and Data Structures

Array A (left sublist) Array A (right sublist)

20 30 40 70 10 50 60
  Applicable part of
i j Algorithm
Now k=2 if (A[i]<= A [j])
temp {
10 20 30 temp [k]  A [i]
if part i  i+1
0 1 2  gets executed k  k+1
k
}
moves ahead
else
{
Note that j A (left sublist) A (right sublist) temp [k]  A [j]
is as it is and j  j+1
only i is 20 30 40 70 10 50 60
k  k+1
incremented   }
i j

A (left sublist) A (right sublist)

Applicable part of
20 30 40 70 10 50 60
Algorithm
  if (A[i]<= A [j])
i j {
temp temp [k]  A [i]
te d
execu i  i+1
10 20 30 40 if part gets k  k+1
 }
k else
{
temp [k]  A [j]
Note that j A (left
sublist) A (right
sublist) j  j+1
remains there k  k+1
and only i is 20 30 40 70 10 50 60 }
incremented  
i j

A (left sublist) A (right sublist)

Applicable part of
20 30 40 70 10 50 60
Algorithm
  if (A[i]<= A [j])
i j {
temp temp [k]  A [i]
10 20 30 40 50 i  i+1
else k  k+1
 gets par }
ex t
k ec else
uted
{
temp [k]  A [j]
Only j A (left sublist) A (right sublist) j  j+1
and k k  k+1
will be 20 30 40 70 10 50 60 }
incremented  
i j

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 54 Introduction to Algorithm and Data Structures

A (left sublist) A (right sublist)

Applicable part of
20 30 40 70 10 50 60
Algorithm
if (A[i]<= A [j])
i j {
temp
temp [k] A [i]
10 20 30 40 50 60 i i+1
k k+1
k }
else else
part of algorithm
{
gets executed
temp [k] A [j]
i remains as A (left sublist) A (right sublist) j j+1
it is but the k k+1
right sublist 20 30 40 70 10 50 60 }
is over
i j

A (left sublist) A (right sublist)

Applicable part of
20 30 40 70 10 50 60
Algorithm
While (i<= mid)
i j {
temp
ecuted temp[k] A[i]
10 20 30 40 50 60 70 t his part get s ex i i+1
k k+1

This part is executed

as j > high

Finally we will copy all the elements of array temp to array A. Thus array A
contains sorted list.
A

10 20 30 40 50 60 70

1.16.2 Greedy Strategy

· This method is popular for obtaining the optimized solutions.

· In Greedy technique, the solution is constructed through a sequence of steps, each
expanding a partially constructed solution obtained so far, until a complete
solution to the problem is reached.
· In Greedy method following activities are performed.
1. First we select some solution from input domain.
2. Then we check whether the solution is feasible or not.

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 55 Introduction to Algorithm and Data Structures

3. From the set of feasible solutions, particular solution that satisfies or nearly
satisfies the objective of the function. Such a solution is called optimal solution.
4. As Greedy method works in stages. At each stage only one input is considered
at each time. Based on this input it is decided whether particular input gives
the optimal solution or not.

1.16.2.1 Example of Greedy Method

· Dijkstra's Algorithm is a popular algorithm for finding shortest path using Greedy
method. This algorithm is called single source shortest path algorithm.
· In this algorithm, for a given vertex called source the shortest path to all other
vertices is obtained.
· In this algorithm the main focus is not to find only one single path but to find the
shortest paths from any vertex to all other remaining vertices.
· This algorithm applicable to graphs with non-negative weights only.
Consider a weighted connected graph as given below.
3
B D
4 8
1 7
A C E
8 3

Now we will consider each vertex as a source and will find the shortest distance
from this vertex to every other remaining vertex. Let us start with vertex A.

Source Distance with other vertices Path shown in graph

vertex
3
A A-B, path = 4 B D
A-C, path = 8 4 8
1 7
A-D, path = ¥ A C E
A-E path = ¥ 8 3
3
B B-C, path = 4 + 1 B D
B-D, path = 4 + 3 4 8
1 7
B-E path = ¥
A C E
8 3
3
C C-D, path = 5 + 7 = 12 B D
C-E, path = 5 + 3 = 8 4 8
1 7
A C E
8 3

D D-E, path = 7 + 8 = 15

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge
Fundamentals of Data Structures 1 - 56 Introduction to Algorithm and Data Structures

But we have one shortest distance obtained from A to E and that is A - B - C - E

with path length = 4 + 1 + 3 = 8. Similarly other shortest paths can be obtained by
choosing appropriate source and destination.

Pseudo Code
Algorithm Dijkstra(int cost[1…n,1…n],int source,int dist[])

for i ¬ 0 to tot_nodes
{
dist[i] ¬ cost[source,i]//initially put the
s[i] ¬ 0 //distance from source vertex to i
//i is varied for each vertex
path[i] ¬ source//all the sources are put in path
}
s[source] ¬ 1 Start from each source node
for(i ¬ 1 to tot_nodes)
{
min_dist ¬ infinity;
v1 ¬ -1//reset previous value of v1
for(j ¬ 0 to tot_nodes-1)
{
Finding minimum
if(s[j]=0)then distance from
{ selected source
if(dist[j]<min_dist)then node.That is :
{ source-j represents
min_dist. edge
min_dist ¬ dist[j]
v1 ¬ j
}
}
}
s[v1] ¬ 1
for(v2 ¬ 0 to tot_nodes-1)
{
if(s[v2]=0)then
{
if(dist[v1]+cost[v1][v2]<dist[v2])then
{
dist[v2] ¬ dist[v1]+cost[v1][v2]
path[v2] ¬ v1
} v1 is next selected destination
} vertex with shortest distance.
All such vertices are
} accumulated in array
} path[ ]
}

®
TECHNICAL PUBLICATIONS - An up thrust for knowledge