Noida Institute of Engineering and Technology, Greater Noida

INTRODUCTION TO DATA STRUCTURES AND

ALGORITHMS

Unit: 1

SUBJECT NAME:- DATA STRUCTURES AND

ALGORITHMS-I
FACULTY NAME: Chandrapal Singh Arya
SUBJECT CODE:- (BCSE 0301)
DESIGNATION : Assistant Professor
COURSE: B.Tech DEPARTMENT: Data Science
COLLEGE:- NIET, GREATER NOIDA
BRANCH: DS-III SEM
SECTION: B
 Evaluation Scheme

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 2

 SYLLABUS
UNIT-I: Introduction to Data Structure and Algorithms

Algorithms, Analyzing Algorithms, Complexity of Algorithms,

Asymptotic notations (Big Oh, Big Theta and Big Omega). Growth of
Functions, Time and Space Complexity of an algorithm, Methods of
solving Recurrences.
Data types: Primitive and Non-Primitive, Introduction to Data structure,
Types of Data Structures- Linear & Non-Linear Data Structures.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 3

 SYLLABUS
UNIT-II: Design and Analysis of Algorithms: Array Data Structure

Arrays: Definition, Single and Multi-Dimensional, Representation of an Arrays: Row and Column
Major, Derivation of Index Formulae for 1-D,2-D and 3-D and n-D Arrays, Application of Arrays:
Sparse Matrix and their Representation.
Searching and Sorting: Searching Algorithms with analysis: Linear and Binary Search.
Sorting Algorithms with analysis: Bubble Sort, Insertion Sort, Selection Sort, Shell Sort, Sorting
in Linear Time- Counting Sort.
Hashing: Hashing the Symbol Table, Hashing Functions, Collision Resolution, Techniques hashing
for direct files.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 4

 SYLLABUS
UNIT-III: Design and Analysis of Algorithms: Linked Data Structure

Linked Lists: Comparison of Array, List and Linked list.

Types of linked list: Singly Linked List, Doubly Linked List, Circular Linked
List.
Polynomial Representation and Addition of Polynomials.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 5

 SYLLABUS
UNIT-IV: Design and Analysis of Algorithms: Stack Data Structure, Recursion
and Queue Data Structure.

Stack Primitive Stack operations: Push & Pop, Array and Linked List Implementation of Stack, Application
of stack: Infix, Prefix, Postfix Expressions and their mutual conversion, Evaluation of postfix expression.
Recursion: Principles of recursion, Tail recursion, Removal of recursion, with example such as Fibonacci
series, binary search, Merge sort and Quick sort algorithms with analysis. Tower of Hanoi, Trade-offs
between iteration and recursion.
Queue: Array and linked List implementation of queues, Operations on Queue: Create, Insert, Delete, Full
and Empty, Circular queues, Dequeue and Priority Queue algorithms with analysis .

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 6

 SYLLABUS
UNIT-V: Design and Analysis of Algorithms: Divide and Conquer and
Greedy Algorithms.

Divide and Conquer concepts with Examples Such as Quick sort, Merge sort, Convex Hull.
Greedy Methods with Examples Such as Activity Selection, Task Scheduling, Fractional Knapsack
Problem.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 7

 BRANCH-WISE APPLICATIONS

OPTIMIZATION: Enhancing DATABASE MANAGEMENT: Use data

performance of software and hardware structure like B-tree and hashing for
through efficient algorithms efficient data storage and retrieval.

COMPUTER SCIENCE
AND ENGINEERING

OPERATING SYSTEM: Implementation

NETWORKING: Algorithms for routing,
of scheduling algorithm, memory
data compression and error detection.
management and file management.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 8

 BRANCH-WISE APPLICATIONS

MACHINE LEARNING: Use of algorithms NATURE LANGUAGE PROCESSING:

like decision tree, neural networks and Algorithms for parsing, sentiment
clustering for learning of data. analysis and machine translation.

COMPUTER SCIENCE
AND ENGINEERING (AI)

SEARCH ALGORITHMS: Implementing PATTERN RECOGNISTION: Efficiently

A*, Minimax for problem-solving and classify and detect patterns in data
game-playing using suitable data structures

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 9

 BRANCH-WISE APPLICATIONS

REINFORCEMENT LEARNING: Algorithms like

DEEP LEARNING: Implement and optimize
Q-training for decision making strategy
neural network architectures.
development.

COMPUTER SCIENCE AND

ENGINEERING(AIML)

MODEL EVALUATION: Algorithms for cross-

FEATURE ENGINEERING: Use data structures
validation and hyper parameter tuning to
for efficient feature extraction and selection.
enhance model performance.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 10

 BRANCH-WISE APPLICATIONS

DATA MINING: Algorithm for clustering, BIG-DATA ANALYTICS: Data Structures

classification and association rule like Hadoop Distributed File System
learning. (HDFS) and MapReduce Algorithms.

COMPUTER SCIENCE
AND ENGINEERING(DS)

PREDICTIVE ANALYSIS: Use time-series DATA CLEANING: Efficiently handle and

algorithms and regression model to preprocess large datasets using suitable
forecast trends. data structures.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 11

 BRANCH-WISE APPLICATIONS

SENSOR DATA PROCESSING: Algorithms NETWORK PROTOCOLS: Design and

for real-time data collection, filtering and Analysis of Algorithms for efficient data
analysis. transmission in IoT networks.

COMPUTER SCIENCE
AND ENGINEERING(IoT)

SECURITY: Implementing algorithms for

EDGE COMPUTING: Optimize algorithms
encryption, authentication and intrusion
for data processing on edge devices.
detection in IoT system.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 12

 BRANCH-WISE APPLICATIONS

INTRUSION DETECTION: Use of data structures

CRYPTOGRAPHY: Design and analyze algorithms
for pattern matching to detect unauthorized
for secure communication.
access.

COMPUTER SCIENCE AND

ENGINEERING (CYBER
SECURITY)

NETWORK SECURITY: Implement and analyze

MALWARE ANALYSIS: Algorithms to detect and
algorithms for firewall and secure routing
analyze malicious code.
protocols

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 13

 Course Objectives
STUDENTS WILL TRY TO LEARN:

1. To impart the basic concepts of data structures and algorithms.

2. To understand concepts about searching and sorting techniques.

3. To Understand basic concepts about stacks, queues, lists, trees and graphs.

4. To understanding about writing algorithms and step by step approach in solving problems

with the help of fundamental data structures.

 COURSE OUTCOMES (CO’s)

At the end of course, the student will be able to:

CO1 : Understand the concept of data structures, algorithm analysis and it’s importance for problem
solving.

CO2 : Implementation of Arrays for searching and sorting and hashing to foster critical thinking.

CO3 : Compare and contrast linked lists with arrays and implementation of linked lists with its
application.

CO4 : Understand static and dynamic implementation of stacks and queues while mastering
principle of recursion for effective problem-solving.

CO5 :Implementation and analysis of divide and conquer algorithms and greedy
approach for efficient problem-solving across diverse contexts.
 PROGRAM OUTCOMES (PO’s)

Engineering Graduates will be able to:

PO1 : Engineering Knowledge

PO2 : Problem Analysis

PO3 : Design/Development of solutions

PO4 : Conduct Investigations of complex problems

PO5 : Modern tool usage

PO6 : The engineer and society

 PROGRAM OUTCOMES (PO’s)

Engineering Graduates will be able to:

PO7 : Environment and sustainability

PO8 : Ethics

PO9 : Individual and teamwork

PO10 : Communication

PO11 : Project management and finance

PO12 : Life-long learning

 COs-POs MAPPING

Sr. No Course Outcome

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12

1 BCSE0301.1 3 3 2 2 1 - - - 1 1 - 2

2 BCSE0301.2 3 3 3 2 2 2 1 - - 1 - 2

3 BCSE0301.3 3 3 3 2 2 1 - - - 1 - 2

4 BCSE0301.4 3 3 3 2 2 1 1 - - 2 - 2

5 BCSE0301.5 3 3 3 3 2 2 - - 1 2 1 2

6 Average

3 3 2.8 2.2 1.8 1.2 0.4 0 0.4 1.4 0.2 2

 PROGRAM SPECIFIC OUTCOMES (PSO’s)

S.NO PROGRAM SPECIFIC PSO DESCRIPTION

OUTCOMES (PSO)

1 PSO1 Identify, analyze real world problems and design their ethical solutions using artificial
intelligence, robotics, virtual/ augmented reality , data analytics, block chain technology
and cloud computing.

2 PSO2 Design and Develop the hardware sensor devices and related interfacing software
systems for solving complex engineering problems.

3 PSO3 Understanding inter-disciplinary computing technique and to apply them in the design of
advanced computing.

4 PSO4 Conduct investigation of complex problems with the help of technical, managerial,
leadership qualities, and modern engineering tools provided by industry-sponsored
laboratories.
 CO’s-PSO’s MAPPING

PSO1 PSO2 PSO3 PSO4

BCSE0301.1 3 2 2 2

BCSE0301.2 2 3 2 2

BCSE0301.3 2 1 3 2

BCSE0301.4 2 2 2 3

BCSE0301.5 3 2 2 3

Average
 PROGRAM EDUCATIONAL OBJECTIVES (PEO’s)
PROGRAM PEO’s DESCRIPTION
EDUCATIONAL
OBJECTIVES (PEO’s)

PEO1 To have an excellent scientific and engineering breadth so as to comprehend, analyze, design
and provide sustainable solutions for real-life problems using state-of-the-art technologies.

PEO2 To have a successful career in industries, to pursue higher studies or to support

entrepreneurial endeavors and to face the global challenges.

PEO3 To have an effective communication skills, professional attitude, ethical values and a desire to
learn specific knowledge in emerging trends, technologies for research, innovation and
product development and contribution to society.

PEO4 To have life-long learning for up-skilling and re-skilling for a successful professional career as
an engineer, scientist, entrepreneur or bureaucrat for the betterment of the society.
PATTERN OF END SEMESTER EXAMINATION (100 MARKS)
PATTERN OF END SEMESTER EXAMINATION (100 MARKS)
PATTERN OF END SEMESTER EXAMINATION (100 MARKS)
PATTERN OF END SEMESTER EXAMINATION (100 MARKS)
PATTERN OF END SEMESTER EXAMINATION (100 MARKS)
 PRE-REQUISITE FOR THE SUBJECT

S.NO TOPIC UNDERSTANDING

1 PROGRAMMING BASIC UNDERSTANDING OF C AND

PYTHON.

2 ARRAYS CREATION OF ARRAYS

3 POINTERS BASIC UNDERSTANDING OF WORKING

WITH POINTERS (C LANGUAGE)

4 CLASS CREATION OF CLASS AND IT’S OBJECTS.

5 FLOW CHART AND ALGORITHMS BASIC SYMBOLS AND PSEUDO CODE.

 BRIEF INTRODUCTION ABOUT THE SUBJECT WITH VIDEOS

Video Links:

1. https://infyspringboard.onwingspan.com/web/en/app/toc/lex_auth_0125409699132620801065_shared/overview

2. https://infyspringboard.onwingspan.com/web/en/app/toc/lex_auth_0135015662906327049522/overview

3. https://infyspringboard.onwingspan.com/web/en/app/toc/lex_auth_01317717336104140852_shared/overview

Above Links will give you a brief reference of Subject.

 UNIT-1 CONTENT
S.NO TOPIC
1 INTRODUCTION TO DATA STRUCTURES
2 NEED OF DATA STRUCTURES
3 WHAT IS AN ALGORITHM
4 ALGORITHMS ANALYSING
5 COMPLEXITY OF AN ALGORITHM
6 ASYMPTOTIC NOTATIONS
1. Big-Oh
2. Big-Theta
3. Big-Omega

7 GROWTH OF A FUNCTIONS.
8 TIME AND SPACE COMPLEXITY OF AN ALGORITHM
9 METHOD OF SOLVING RECURRENCES.
10 WHAT IS DATA TYPES.
1. PRIMITIVE AND NON-PRIMITIVE

11 TYPES OF DATA STRUCTURES:

1. LINEAR DATA STRUCTURES
2. NON-LINEAR DATA STRUCTURES
 UNIT-1 OBJECTIVE

After the completion of 1st unit, Student will be able to understand the
following:
• Basic Understanding of an Algorithm.
• Able to calculate the complexity of an algorithm.
• Will be able to identity the asymptotic notation and the level of
complexity.
• Different types of Data Structures.
• Will be able to solve the recurrence relations.
 INTRODUCTION: WHAT IS DATA STRUCTURES ?

• What is Data Structures?

A Data Structures is a specialized format for organizing, processing, retrieving
and storing data. It is a way of arranging data on a computer so that it can be
accessed and updated efficiently.

Data: A value or a set of values of different type which is called data types
like string, integer, char etc.

Structures: Way of organizing information, so that it is easier to use.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 31

 INTRODUCTION: WHAT IS DATA STRUCTURES ?

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 32

 INTRODUCTION: WHY SHOULD WE LEARN DATA STRUCTURES ?

• PROBLEM SOLVING

• ALGORITHM DESIGN

• REQUIREMENTS FOR THE JOB

• COMPETETIVE PROGRAMMING

• BETTER UNDERSTANDING OF COMPUTER SCIENCE

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 33

 INTRODUCTION: WHY DATA STRUCTURES ARE IMPORTANT?

• PERFORMANCE: Choosing the right data structure significantly impacts how

quickly your program can access and process information. For example, searching
an unsorted list takes much longer than searching a sorted array.

• MEMORY MANAGEMENT: Data structures help optimize memory usage,

preventing wasted space and improving program efficiency.

• CODE REUSABILITY: Well-defined data structures can be reused across different

parts of your program or even other programs, saving development time and
promoting consistency.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 34

 INTRODUCTION: WHAT IS THE NEED OF DATA STRUCTURES ?

• DATA STRUCTURES ARE NEEDEED BECAUSE:

• They provide efficient solutions to organizing and manipulating data.

• They help to store and retrieve data in an organized manner, making it easier to
manage and analyze the information.

Some more specific reasons are listed in as follows:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 35

 INTRODUCTION: WHAT IS THE NEED OF DATA STRUCTURES ?

1. Improved Time Complexity

2. Better Space Complexity

3. Efficient Data Retrieval

4. Better Data Management

5. Solving Complex Problems

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 36

 TOPIC OBJECTIVE: ALGORITHMS

The objective of this topic is to make students understand about:

• Need of algorithm
• Problem statement
• Why study algorithm
• Characteristics of Algorithm

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 37

 ALGORITHMS: WHAT IS AN ALGORITHM ?

The word Algorithm means “a process or set of rules to be followed in

calculations or other problem-solving operations”.

Therefore Algorithm refers to a set of rules/instructions that step-by-step define

how a work is to be executed upon in order to get the expected results.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 38

 ALGORITHMS: WHAT IS AN ALGORITHM ?

 An algorithm is any well-defined computational procedure that takes some

value, or set of values, as input and produces some value, or set of values, as
output in a finite amount of time.

Set of rules to
INPUT obtain the OUTPUT
expected
output from
given input

ALGORITHM
 An algorithm is thus a sequence of computational steps that transform the input
into the output.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 39

 ALGORITHMS: WHY WE STUDY ALGORITHMS ?

By studying algorithms, developers can write better programs. Some

examples are as follows:

1. Finding the fastest route in a GPS navigation system

2. Navigating an airplane or a car (cruise control)

3. Finding what users search for (search engine)

4. Sorting, for example sorting movies by rating

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 40
 CHARACTERISTICS OF AN ALGORITHM

Following are the characteristics of an algorithm:

1. WELL-DEFINED INPUT

2. WELL-DEFINED OUTPUT

3. UNAMBIGUITY

4. FINITENESS

5. FEASIBILITY

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 41

 Performance Analysis

• It depends upon two major factors.

• Time Complexity
• Space Complexity

• Time Complexity: The amount of system time an algorithm requires

to run to completion.

• Space Complexity: The amount of memory an algorithm requires to

run to completion.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 42

 Performance Analysis
Analysis based on time and space are of two types
Aspect Prior Analysis Posterior Analysis

Analysis done before running an algorithm or

Definition Analysis done after running an algorithm or experiment.
experiment.

To check how things actually went and see if they matched

Purpose To guess how things will go and plan ahead.
expectations.

Focus Based on theories and predictions. Based on real results and data.

Data Estimated or predicted data. Actual data collected from the experiment.

Techniques Designing algorithms, making predictions. Measuring performance, checking results.

Hardware/Soft
ware Independent of specific hardware or software. Dependent on the actual hardware and software used.
Dependency
8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 43
 TOPIC OBJECTIVE: ANALYSIS OF ALGORITHM

The objective of this topic is to make students understand about:

• Space Complexity
• Time Complexity
• Best Case
• Worst Case
• Average Case

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 44

 ANALYSIS OF ALGORITHM

• The term "analysis of algorithms" was coined by Donald Knuth.

• To estimate the complexity function for arbitrarily large input.

• Analysis of algorithms is the determination of the amount of time

and space resources required to execute it.

• An algorithm's efficiency or running time is stated as a function

relating the input length to the number of steps, known as time
complexity, or volume of memory, known as space complexity.

• The main concern of the analysis of algorithms is the required time

or performance.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 45

 TIME COMPLEXITY OF AN ALGORITHM

• Time complexity is defined as the amount of time taken by an

algorithm to run, as a function of the length of the input. It
measures the time taken to execute each statement of code in an
algorithm.

• Time complexity is commonly estimated by counting the number of

elementary operations performed by the algorithm, supposing that
each elementary operation takes a fixed amount of time to perform.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 46

 ALGORITHM EXAMPLE
3. Factorial of a Number
1. Addition of Two Numbers
START
START
INPUT n
INPUT num1, num2
factorial = 1
sum = num1 + num2
FOR i FROM 1 TO n
OUTPUT sum
factorial = factorial * i
END
END FOR
Constant Time OUTPUT factorial
END
Linear Time
2. Sum of N Natural Numbers
START 4. Check if a Number is Even or Odd
INPUT n
sum = 0 START
FOR i FROM 1 TO n INPUT num
sum = sum + i IF num MOD 2 == 0 THEN
END FOR OUTPUT "Even"
OUTPUT sum ELSE
END OUTPUT "Odd"
END IF
Linear Time END
8/20/2025 Prof. Chandrapal AryaConstant Time
BCSE0301 UNIT-I 47
 ALGORITHM EXAMPLE

function fibonacci_series(n): function is_palindrome(sequence):

a=0 left = 0
b=1 right = length(sequence) - 1
for i from 0 to n-1:
print(a) while left < right:
next = a + b if sequence[left] != sequence[right]:
a=b return false
b = next left = left + 1
right = right - 1

return true

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 48

 ALGORITHM EXAMPLE

Algo 1(n)
{
j=1
for(i=1;i<=n;i=i+2)
{
j=j+1
}
}

푎.푝푎.푝

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 49

 ALGORITHM EXAMPLE

Algo2(n)
{ Algo3(n)
j=1 {
for(i=1;i<=n;i=i*2) j=1
{ for(i=n;i>0;i=i/2)
j=j+1 {
} j=j+1
}
}
푔.푝푔.푝 }

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 50

 ALGORITHM EXAMPLE

Int IsPrime(n)
{
for(i=2;i<= 푛;i=i++)
{
if(n%i == 0)
{
print(“not prime”)
return 0;
}
return 1;
}

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 51

 Time Complexity for nested loops

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
k = i+j
}
}
print(k)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 52

 Time Complexity for nested loops

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=j+2)
{
k = i+j
}
}
print(k)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 53

 Time Complexity for nested loops

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=j*2)
{
k = i+j
}
}
print(k)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 54

 Time Complexity for nested loops

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=j+2)
{
for(k=1;k<=n;k++)
m = i+j+k
}
}
print(m)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 55

 TIME COMPLEXITY OF AN ALGORITHM

Why is time complexity a function of its input size?

To perfectly grasp the concept of "as a function of input size," imagine you have an algorithm that
computes the sum of numbers based on your input. If your input is 4, it will add 1+2+3+4 to output
10; if your input is 5, it will output 15 (meaning 1+2+3+4+5).

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 56

 TIME COMPLEXITY OF AN ALGORITHM

In the above code, we have three statement

• Looking at the image above, we only have three statements. Still, because there is a loop, the second statement will
be executed based on the input size, so if the input is four, the second statement (statement 2) will be executed four
times, meaning the entire algorithm will run six (4 + 2) times.

• In plain terms, the algorithm will run input + 2 times, where the input can be any number. This shows that it's
expressed in terms of the input. In other words, it is a function of the input size.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 57

 TIME COMPLEXITY OF AN ALGORITHM

How to measure time?

Count the total number of fundamental operations in the program and this total
will give a rough estimate of the running time in terms of input size.

• Best Case: The minimum number of steps taken on any instance of size n.

• Average Case: An average number of steps taken on any instance of size n.

• Worst Case: The maximum number of steps taken on any instance of size n.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 58

 TIME COMPLEXITY OF AN ALGORITHM

Running time for Algorithm

• ALGORITHM COST RUNNING TIME
Sum(A,n)
{
S=0 C1 1
for i=1 to n do C2 n+1
s=s+A[i] C3 n
return s C4 1
}

• Total Running Time = c1 + c2(n+1)+c3(n) + c4

• T(n) = Linear function

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 59

 TIME COMPLEXITY OF AN ALGORITHM

COMMON TIME COMPLEXITIES:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 60

 TIME COMPLEXITY OF AN ALGORITHM

1. CONSTANT TIME : O(1)

• An algorithm is said to have a constant time when it is not dependent on the input data (n). No
matter the size of the input data, the running time will always be the same.

EXAMPLE:
If a>b:
return True An algorithm with constant time
Else:
return False complexity is excellent since we don’t
need to worry about the input size.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 61

 TIME COMPLEXITY OF AN ALGORITHM

1. CONSTANT TIME : O(1)

CONSTANT TIME COMPLEXITY GRAPH

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 62
 TIME COMPLEXITY OF AN ALGORITHM

2. LINEAR TIME : O(n)

• An algorithm is said to have a linear time complexity when the running time increases linearly
with the length of the input. When the function involves checking all the values in input data,
with this order O(n). This means that when a function has an iteration that iterates over an
input size of n, it is said to have a time complexity of order O(n).

EXAMPLE:

def linear_search(data,value):
for index in range(len(data)):
if value==data[index]:
return index
raise ValueError(“Value not found in the list”)

If __name__==‘__main__’:
data =[1,2,9,8,3,4,7,6,5]
print(linear_search(data,7))

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 63

 TIME COMPLEXITY OF AN ALGORITHM

2. LINEAR TIME : O(n)

LINEAR TIME COMPLEXITY GRAPH

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 64
 TIME COMPLEXITY OF AN ALGORITHM

3. LOGARITHMIC TIME: O(logn)

• An algorithm is said to have a logarithmic time complexity when it reduces the size of the input
data in each step. This indicates that the number of operations is not the same as the input size.
The number of operations gets reduced as the input size increases.

• This is similar to linear time complexity, except that the runtime does not depend on the input
size but rather on half the input size. When the input size decreases on each iteration or step, an
algorithm is said to have logarithmic time complexity.

• This method is the second best because your program runs for half the input size rather than the
full size. After all, the input size decreases with each iteration.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 65

 TIME COMPLEXITY OF AN ALGORITHM

3. LOGARITHMIC TIME: O(logn)

def binary_search(data,value):
n=len(data)
left=0
right=n-1
while left<=right:
middle=(left+right) // 2
if value < data[middle]:
right=middle-1
if __name__=‘__main__’:
elif value > data[middle]:
data=[1,2,3,4,5,6,7,8,9,10]
left=middle+1 print(binary_search(data,8))
else:
return middle
raise ValueError(“Value not found”)

• P.S.: It is important to understand that an algorithm that must access all elements of its input data cannot
take logarithmic time, as the time taken for reading input of size n is of the order of n.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 66

 TIME COMPLEXITY OF AN ALGORITHM

3. LOGARITHMIC TIME: O(logn)

LOGARITHMIC TIME COMPLEXITY GRAPH

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 67

 TIME COMPLEXITY OF AN ALGORITHM

4. QUASI-LINEAR TIME: O(n log n)

• An algorithm is said to have a quasilinear time complexity when each operation in the input
data has a logarithm time complexity. It is commonly seen in sorting algorithms. It is commonly
seen in sorting algorithms (e.g. merge sort, heap sort).

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 68

 TIME COMPLEXITY OF AN ALGORITHM

5. QUADRATIC TIME: O(n^2)

• An algorithm is said to have a non-linear time complexity where the running time increases non-
linearly (n^2) with the length of the input. Generally, nested loops come under this order where
one loop takes O(n) and if the function involves a loop within a loop, then it goes for O(n)*O(n) =
O(n^2) order.

• EXAMPLE: A perfect way to explain this would be if you have an array with n items. The outer loop will run n
times, and the inner loop will run n times for each iteration of the outer loop, which will give total n^2 prints.
If the array has ten items, ten will print 100 times (10^2).
for x in data:
for y in data:
print(x,y)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 69

 TIME COMPLEXITY OF AN ALGORITHM

5. QUADRATIC TIME: O(n^2)

QUADRATIC TIME COMPLEXITY GRAPH

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 70

 TIME COMPLEXITY OF AN ALGORITHM

6. EXPONENTIAL TIME: O(2^n)

• An algorithm is said to have an exponential time complexity when the growth doubles with each
addition to the input data set.

• Exponential Time Complexity when the growth rate doubles with each addition to the input (n),
often iterating through all subsets of the input elements. Any time an input unit increases by 1,
the number of operations executed is doubled.
• Example: The recursive Fibonacci sequence In the below code, the algorithm specifies a growth
rate that doubles every time the input data set is added. This means the time complexity is
exponential with an order O(2^n).

def Fibonacci(n):
if n<=1:
return n
return Fibonacci(n-1)+Fibonacci(n-2)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 71

 TIME COMPLEXITY OF AN ALGORITHM

7. FACTORIAL TIME: O(n!)

• An algorithm is said to have a factorial time complexity when it

grows in a factorial way based on the size of the input data.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 72

 TIME COMPLEXITY OF AN ALGORITHM

BIG-O Complexity Chart:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 73

 SPACE COMPLEXITY OF AN ALGORITHM

• Space complexity is nothing but the amount of memory space that an algorithm or a problem
takes during the execution of that particular problem/algorithm

• The space complexity is not only calculated by the space used by the variables in the
problem/algorithm it also includes and considers the space for input values with it.

 AUXILLARY SPACE: Auxiliary space is nothing, but the space required by an algorithm/problem
during the execution of that algorithm/problem and it is not equal to the space complexity
because space complexity includes space for input values along with it.

Space Complexity = Auxiliary Space + Space used for input values

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 74

 SPACE COMPLEXITY OF AN ALGORITHM

EXAMPLE:
int sum (int n)
{
int i, sum=0;
for(i=n;i>=1;i--)
sum=sum+i;
return sum;
}

• So in the above example, input value is 'n' that is constant which will take the space of O(1).
Now ,what about auxiliary space, so it is also O(1) because 'i' and 'sum' are also constants.
• Hence,total space complexity is O(1).

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 75

 TOPIC: ASYMPTOTIC NOTATIONS

The Objective of this topic is to make students understand about the five
asymptotic notations:

Asymptotic notation is a mathematical tool of an algorithm to mathematically

represent the time complexity

1. Big-Oh Notations
2. Theta Notations
3. Big-Omega Notations
4. Small Oh Notations
5. Small Omega Notations

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 76

 ASYMPTOTIC NOTATIONS

• What is the meaning of ‘asymptotic’?

Asymptotic is an adjective used in specialized mathematics to describe something that gets closer
to a limit as a variable approaches infinity.

• ASYMPTOTIC NOTATION IN COMPUTER SCIENCE:

“Asymptotic notation is a fundamental concept in computer science and mathematics that allows
us to describe the behavior of algorithms and functions as their input size approaches infinity.”

• Asymptotic notation provides a simplified way to analyze and compare the efficiency of
algorithms, focusing on their growth rates without being concerned with constant factors and
lower-order terms.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 77

 ASYMPTOTIC NOTATIONS

• PURPOSE OF ASYMPTOTIC NOTATIONS:

1. To simplify the running time of the function

2. To describe the behavior of the function.
3. To provide asymptotic bound.
4. To describe how the running time of an algorithm increases with
increase in input size

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 78

 ASYMPTOTIC NOTATIONS: BIG-OH

• Big-oh is the formal method of expressing the upper bound of an algorithm's running time. It is
the measure of the longest amount of time.

• The function f(n) = O(g(n)) (read as “ f of n is big oh of g of n”) if there exist positive constants C
and n0 such that
f(n)≤Cg(n) for all n≥ n0

• IT GIVES THE WORST-CASE COMPLEXITY OF AN ALGORITHM.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 79

 ASYMPTOTIC NOTATIONS: BIG-OH

The function f (n) = O (g (n))

O(g(n)) = { f(n): there exist positive constants c

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

• The above expression can be described as a

function f(n) belongs to the set O(g(n)) if
there exists a positive constant c such that
it lies between 0 and cg(n), for sufficiently
large n.

• For any value of n, the running time of an

algorithm does not cross the time provided
by O(g(n)).

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 80

 ASYMPTOTIC NOTATIONS: BIG-OH

Q1 f(n) = 3n + 4, g(n) = n, Prove f(n) = O(g(n))

Sol.
To prove f(n) = O(g(n)) i.e. f(n) <= c.g(n)
n f(n) c.
It means 3n + 4 <=c.n g(n)
3n+4 5n
Let c= 5 1 7 > 5

2 10 = 10
So, for n0 = 2
3 13 < 15
f(n) < = 5.g(n)
4 16 < 20

Hence f(n) = O(g(n))

Prof. Chandrapal Arya BCSE0301 UNIT-I

8/20/2025 81
 ASYMPTOTIC NOTATIONS: BIG-OH

• CONSIDER THIS EXAMPLE:

f(n)=3n+2
g(n)=n
If we want to represent f(n) as O(g(n)) then it must satisfy f(n) <= C g(n) for
all values of C > 0 and n0 =1
f(n)<=Cg(n)
3n + 2 <= C n

• The above condition is always TRUE for all values of C = 4 and n >= 2 .By
using Big - Oh notation we can represent the time complexity as
follows...3n + 2 = O(n)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 82

 ASYMPTOTIC NOTATIONS: BIG-OH

• CONSIDER THIS EXAMPLE:

Let us consider a given function, f(n)=4.n3+10.n2+5.n+1

Considering g(n)=n3

f(n)⩽5.g(n) for all the values of n>2.

Hence, the complexity of f(n) can be represented as: O(g(n)), i.e. O(n3)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 83

 ASYMPTOTIC NOTATIONS: BIG-OMEGA

• Big-Omega notation defines the lower bound of an algorithm in terms of Time

Complexity.

• Big-Omega notation always indicates the minimum time required by an

algorithm for all input values.

• Big-Omega notation describes the best case of an algorithm time complexity.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 84

 ASYMPTOTIC NOTATIONS: BIG-OMEGA

• Consider function f(n) as the time complexity of an algorithm and g(n) is the
most significant term.

• If f(n) >= C g(n) for all n >= n0, C > 0 and n0 >= 1. Then we can represent f(n) as
Ω(g(n)). f(n) = Ω(g(n))

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 85

 ASYMPTOTIC NOTATIONS: BIG-OMEGA

CONSIDER THIS EXAMPLE:

• f(n) = 3n + 2
• g(n) = n

If we want to represent f(n) as Ω(g(n)) then it must

satisfy f(n) >= C g(n) for all values of C > 0 and n0>=
1
f(n) >= C g(n)
⇒3n + 2 >= C n

The above condition is always TRUE for all values of

C = 1 and n >= 1.
By using Big-Omega notation we can represent the
time complexity as follows...3n + 2 = Ω(n)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 86

 • Q1 f(n) = 3n + 4, g(n) = n, Prove f(n) = Ω (g(n))

• Q2 f(n) = 푛, g(n) = log2 푛 , Prove f(n) = Ω (g(n))

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 87

 ASYMPTOTIC NOTATIONS: THETA

• Theta notation defines the average bound of an algorithm in terms of Time

Complexity.

• That means Theta notation always indicates the average time an algorithm
requires for all input values.

• Theta notation describes the average case of analgorithm’s time complexity.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 88

 ASYMPTOTIC NOTATIONS: THETA

• Consider function f(n) as the time complexity of an algorithm and g(n) is the most
significant term.

• If C1 g(n) <= f(n) <= C2 g(n) for all n >= n0, C1 > 0, C2 > 0 and n0 >= 1. Then we
can represent f(n) as Θ(g(n))
f(n) = Θ(g(n))

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 89

 ASYMPTOTIC NOTATIONS: THETA

• Q1 f(n) = 10푛2 푙표푔2 푛 + 3n + 4, g(n) = 푛2 푙표푔2 푛 , Prove f(n) = θ(g(n))

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 90

 ASYMPTOTIC NOTATIONS: THETA

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 91

 Small o Notation(o)

• Small-o, commonly written as o, is an Asymptotic Notation

to denote the upper bound (that is not asymptotically tight)
on the growth rate of runtime of an algorithm.
o(g(n)) = { f(n): there exist positive constants c and n0 such
that
0 <= f(n) < c*g(n) for all n >= n0}

• Another definition for o notation:

f(n) = o(g(n)) if and only if
lim(n→∞)f(n)/g(n)=0

Prof. Chandrapal Arya BCSE0301 UNIT-I

8/20/2025 92
 Another Definition for o notation.

f(n) = o(g(n)) if and only if Q Justify n! = o(푛푛)

푓(푛)
lim∞
푛→ =0
푔(푛)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 93

 Small omega Notation(w)

• Small-omega, commonly written as w, is an Asymptotic Notation to denote the lower

bound (that is not asymptotically tight) on the growth rate of runtime of an algorithm.
w(g(n)) = { f(n): there exist positive constants c and n0 such that
f(n) > c*g(n)>=0 for all n >= n0}

• Another definition for o notation:

f(n) = o(g(n)) if and only if
lim(n→∞)g(n)/f(n)=0

Prof. Chandrapal Arya BCSE0301 UNIT-I

8/20/2025 94
 Another Definition for w notation.

f(n) = w(g(n)) if and only if

푔(푛)
lim∞
푛→ =0
푓(푛)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 95

 TOPIC: RECURRENCE RELATION

OBJECTIVE: After going through this topic students will be able to

• Define recurrence relation.

• Construct recurrence relation of simple recursive algorithms.
• List the techniques used to solve recurrence relation.
• Solve the recurrence relation through, Substitution, Recurrence Tree & Master
methods.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 96

 TOPIC: RECURRENCE RELATION

• We often use a recurrence relation to describe the running time of a recursive

algorithm.

• A recursive algorithm can be defined as an algorithm which makes a recursive call

to itself with a smaller data size.

• Like all recursive functions, a recurrence relation also consists of two steps:
i. One or more initial conditions
ii. Recursive definition of a problem

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 97

 TOPIC: RECURRENCE RELATION

• Example 1:
• A Fibonacci sequence 0, 1, 2, … .. can be defined by the recurrence relation as:
0 =0
= {0 =1
−1 + −2 ≥2

1. (Basic Step): The given recurrence says that if n=0 then = 0 and if n=1 then 1 = 1 . These
0
two conditions (or values) where recursion does not call itself is called an initial condition (or
Base conditions).
2. (Recursive Step): This step is used to find new terms 2, 3, … . ., from the existing (preceding)
terms, by using the formula = −1 + −2 for ≥ 2.

This formula says that “by adding two previous sequencese (or term) we can get the next term”.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 98

 TOPIC: RECURRENCE RELATION

• Example 1:
• A Fibonacci sequence 0, 1, 2, … .. can be defined by the recurrence relation as:
0 =0
= {0 =1
−1 + −2 ≥2

1. (Basic Step): The given recurrence says that if n=0 then = 0 and if n=1 then 1 = 1 . These
0
two conditions (or values) where recursion does not call itself is called an initial condition (or
Base conditions).
2. (Recursive Step): This step is used to find new terms 2, 3, … . ., from the existing (preceding)
terms, by using the formula = −1 + −2 for ≥ 2.

This formula says that “by adding two previous sequencese (or term) we can get the next term”.
For example = + = + = ; 3 = 2 + 1 = 1 + 1 = 2 ; 4 = 3 + 2 = 2 + 1 = 3 and so on

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 99

 TOPIC: RECURRENCE RELATION

• Example 2:
Find out the value of n! = n (n-1) (n-2)……. (3) (2) (1) for n ≥ 1
The factorial function is defined as:
!={1 =1 .
( − 1)! >1

Let us write an algorithm for factorial function:

int fact(int n)
== 0 ℎ
1

∗ ( − 1)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 100

 TOPIC: RECURRENCE RELATION

• Let us try to understand the efficiency of the algorithm in terms of the number of
multiplication operations required for each value of n
Let ( ) denote the number of multiplications required to execute the n!, that is T(n)
denotes the number of times line 4 is executed in the factorial algorithm.

• We have the initial condition T(0)=1; since when n=0,fact simply returns
• When n>1 ,the line performs the multiplication plus fact is recursively called the
input (n-1). It means, by the definition of (n), additional (n-1) number of
multiplication are required.

We can write a recurrence relation for the

T(n ) = { 1, =0
1 + ( − 1)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 101

 TOPIC: METHODS FOR SOLVING RECURRENCE RELATION

• Three methods are discussed here to solve recurrence relations:

1. The Master Method

2. The Recursion Tree Method
3. Iteration Method
4. Substitution Method

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 102

 TOPIC: SUBSTITUTION METHOD

• Substitution is the opposite of induction .We start at n and move backward. A

substitution method is one, in which we guess a bound and then use
mathematical induction to prove whether our guess is correct or not?. It
comprises two steps:

Step 1: Guess the asymptotic bound of the Solution.

Step 2: Prove the correctness of the guess using Mathematical

Induction.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 103

 TOPIC: SUBSTITUTION METHOD

• Example 1:Solve the following recurrence by using the substitution method.

푛
푇 푛 = 2푇 +푛
2
• Solution: Step 1: The given recurrence is quite similar to that of the
Merge Sort algorithm. Therefore, our guess to the solution is ( ) =
( ) Or ( ) ≤ .

• Step 2: Now we use mathematical Induction.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 104

 TOPIC: SUBSTITUTION METHOD

• Here our guess does not hold for n=1because (1) ≤ . 1 1 . .( )≤0 ℎ ℎ
ℎ (1) = 1.

• Now for n=2

=(2) ≤ . 2 2 2
2
=2푇 + 2 ≤ 푐.2
2
=2(1)+2≤c.2
=0+2 ≤c.2

2 ≤c.2 which is true. So, (2) ≤ c.nlogn is True for n=2

So, (2) ≤ c.nlogn is True form=2.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 105

 TOPIC: SUBSTITUTION METHOD

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 106

 TOPIC: SUBSTITUTION METHOD

• Warning: Using the substitution method, it is easy to prove a weaker bound

than the one you're supposed to prove. For instance, if the runtime is O(n), you
might still be able to substitute cn2 into the recurrence and prove that the
bound is O(n2). Which is technically true, but don't let it mislead you into
thinking it's the best bound on the runtime. People often get burned by this on
exams!

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 107

 TOPIC: RECURSION TREE METHOD

• A recursion tree is a tree where each node represents the cost of a certain
recursive sub-problem. Then you can sum up the numbers in each node to get
the cost of the entire algorithm.

Why is it used?
• A recursion tree is mainly used to generate a close guess to the actual
complexity, which can be further verified using the substitution method. So, we
should keep in mind that we can use recursion trees to develop an intuition of
the underlying pattern, but they are not the actual proofs.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 108

 TOPIC: STEPS OF RECURSION TREE METHOD

• Step 1: Construct a recursion tree from the recurrence relation at hand.

• Step 2:
• Find the total number of levels in the recursion tree.
• Compute the cost of each level in the tree.
• Calculate the total number of nodes in the last level or the leaf nodes.
• Compute the cost of the last level.

• Step 3: Sum up the cost of all the levels and decompose the expression obtained
in the standard asymptotic notation.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 109

 TOPIC: STEPS OF RECURSION TREE METHOD

The Recursion tree method is especially used to solve a recurrence of

the form:
풏
푻 풏 = 풂푻 + 풏
풃
where a>1, b≥1

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 110

 TOPIC: STEPS OF RECURSION TREE METHOD

We make a recursion tree for a given recurrence as follows:

To make a recursion tree of a given recurrence. First, put the value of ( ) at
the root node of a tree and make a number of child nodes of this root value f(n). Now tree will look
like as:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 111

 TOPIC: STEPS OF RECURSION TREE METHOD

풏
• Now we have to find the value of 푻 by putting (풏 / 풃)in place of n
풃
in equation .That is
풏
풏 풃 풏
• = 푻 = 풂푻 + 풇( )
풃 풃 풃
풏 풏
• = 풂푻 + 풇 ퟐ + 풇( )……………(ii)
풃 풃

• From equation (2), now ( ⁄ ) will be the value of node having a branch (child
풏 풏
nodes) each of size 푻 Now each 푻 in the figure in previous slide will be
풃 풃
replaced as follows:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 112

 TOPIC: STEPS OF RECURSION TREE METHOD

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 113

 TOPIC: STEPS OF RECURSION TREE METHOD

• Now you have to find the per-level cost of a tree. Per-level cost is the sum
of the cost of each node at that level. For example, per level cost at level 1
is:
푛 푛 푛
+푓 + …푓 푎 푡푖푚푒푠 . This is called “Row-Sum”.
푏 푏 푏

• Now the total (final) cost of the tree can be obtained by taking the sum of
the cost of all these levels. i.e.,

푇표푡푎푙 퐶표푠푡 = 푠푢푚 표푓 푐표푠푡푠 표푓 푙0 + 푙1 + ………. + 푙푘 .

This is known as “Column-Sum”.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 114

 TOPIC: RECURSION TREE METHOD

풏
• Example 1: Solve the recurrence 풏 = ퟐ푻 + 풏 using the recursion tree
ퟐ
method.
Solution:

Step 1: First you make a recursion tree of a given recurrence:

1. To make a recursion tree, you have to write the value of ( ) at root node.
2. The number of child of a Root Node is equal to the value of a. (Here the value
of a = 2).So recursion tree be looks like as:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 115

 TOPIC: RECURSION TREE METHOD

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 116

 TOPIC: RECURSION TREE METHOD

풏
Step 2: Now we have to find the value of T in figure a by putting (n/2) in place
ퟐ
of n in equation i.e.,

풏
풏 ퟐ 풏
푻 = ퟐ푻 + 풏 = ퟐ푻 ퟐ + 풏 / ퟐ
풃 ퟐ ퟐ
From above equation, now (n/2) will be the value of node having 2 branch (child
nodes) each of size T(n/2) in figure a will be replaced as follows:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 117

 TOPIC: RECURSION TREE METHOD

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 118

 TOPIC: RECURSION TREE METHOD

• In this way, you can extend a tree upto Boundary Condition (when problem size
becomes 1). So, the final tree will look like:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 119

 TOPIC: RECURSION TREE METHOD

• Now we find the per-level cost of a tree, Per-level cost is the sum of
the costs within each level.
풏 풏 풏 풏
ퟐ
+ ( ퟐ) + ( ퟐ)+ ( ퟐ)=n
ퟐ ퟐ ퟐ ퟐ

• Then total cost is the sum of the cost of all levels which gives the solution of
recurrence. The height of the tree is:
푻풐풕풂풍 푪풐풔풕 = 풏 + 풏 + 풏 + 풏………. + 풏

“To find the sum of the series you have to find the total numbers of the term in
the series. To find the total number of terms, you have to find the height of tree.”

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 120

 TOPIC: RECURSION TREE METHOD

• The height of the tree can be obtained by watching Figure c, you start a problem
푛
size n, then problem size is reduced to (n/2) , then ( 2) and so on till boundary
2
condition of problem size 1 is not reached, i.e.,.

풏 풏 풏
풏→ → ퟐ …………→ 풌
ퟐ ퟐ ퟐ
• At last problem size will be equal to 1 if:
풏 풌→풌 = 풍풐품 풏.
= ퟏ→풏 = ퟐ ퟐ
ퟐ풌
• This k represents the height of the tree, hence height = 풌 = 풍풐품ퟐ풏
• Total Cost is: 풏 + 풏 + 풏 + 풏………. + 풍풐품ퟐ풏 terms
=풏풍풐품ퟐ풏

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 121

 TOPIC: MASTER METHOD

• Definition 1: A function f(n) is asymptotically positive if any only if there exists a

real number n such that f(x)>0 for all x>n.

• The master method provides us a straight forward method for solving recurrences
풏
of the form : 푻 풏 = 풂푻 + 풇 풏 ,풘풉풆풓풆 풂 ≥ ퟏ 풂풏풅 풃 > ퟏ are constants
풃
and f(n) is an asymptotically positive function.

• This recurrence gives us the running time of an algorithm that divides a problem
of size n into sub-problems of size (n/b).

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 122

 TOPIC: MASTER METHOD

• Master Theorem: The Master Method requires memorization of the following 3 cases:

Let 푻(풏) be defined on the non-negative integers by:

풏
푻 풏 = 풂푻 + 풇 풏 ,풘풉풆풓풆 풂 ≥ ퟏ 풂풏풅 풃 > ퟏ
풃
Then 푻(풏) can be bounded asymptotically as follows:

풂−풆 풃 풂
CASE 1: IF 풇(풏) = 푶 풏풍풐품풃 풇풐풓 풔풐풎풆 ϵ>0 ,then 푻 풏 = 휽(풏풍풐품 )

풂 풃 풂
CASE 2: IF 풇(풏) = ϴ 풏풍풐품풃 , then 푻 풏 = 휽(풏풍풐품 .풍풐품풏)

풍풐품풃풂+ϵ 풏
CASE 3: IF (풏)= (풏 ) 풇풐풓 풔풐풎풆 ϵ > ퟎ, 풂풏풅 풊풇 풂풇 ≤ 풄풇 풏 풇풐풓
풃
someconstant c<1 and all sufficientlyProf.
8/20/2025
large 풏.푻Arya풏
Chandrapal = 휽(풇 풏 UNIT-I
BCSE0301 ) 123
 TOPIC: MASTER METHOD

• REMARKS: To apply the Master method you always compare 풏풍풐품풃풂 and f( )The larger of the
two functions determines the solution to the recurrence problems. If the growth rate of these two
functions then it belongs to case 2. In this case, we multiply by a logarithmic factor to get the run
time solution (T(n)) of the recurrence relation.

• If 풇(풏) is polynomially smaller than 풏풍풐품풃(by a factor of 풏 ∈ then case 1 will be

applicable to find ( ).

• If 풇(풏) is polynomially larger than 풏풍풐품풃풂 (by a factor of ퟏ / 풏 ∈ then 푻 풏

= 휽(풇 풏 which is in case 3.)

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 124

 TOPIC: MASTER METHOD
푛
• Example 1:Consider the recurrence of 푇 푛 = 9푇 + 푛in which a=9, b=3, 푓 푛
풂 − 풆
3
= 푛, 푛푙표푔푏푎=푛2 and f(n)=푶 풏풍풐품풃 , where ϵ=1.The growth

rate of f(n) is slower, we will apply the case 1 of Master Theorem and we get ( )
풂−풆
=Θ(풏풍풐품풃 )= Θ(푛2).

ퟐ풏
• Example 2:Consider the recurrence of 푻 풏 = 푻 + ퟏ, in which = 1, 3 =
ퟑ
3/2 ,푓 푛 = 푛푙표푔32 = 1. Since f( ) = (푛푙표푔32). By Master Theorem (case2), we
get ( ) = Θ(푛푙표푔푏푎 . ) = Θ( ).

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 125

 TOPIC: RECURSION TREE METHOD

• PRACTICE QUESTION:

풏 ퟐ풏
1. Solve the recurrence 푻 풏 = 푻 +푻 + 풏 using recursion tree method.
ퟑ ퟑ
2. A recurrence relation for Tower of Hanoi (TOH) problem is 푻 풏 = ퟐ푻 풏 − ퟏ
+ ퟏ with (1)=1 and T(n)=3. Solve this recurrence to find the solution of TOH
problem.
3. Solve the following recurrence using the recursion tree method:
풏
d) 푻 풏 = ퟒ푻 + 풏
ퟐ
풏 풏 풏
e) 푻 풏 = 푻 + 푻 + 푻 + 풏
ퟐ ퟒ ퟖ

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 126

 TOPIC: RECURSION TREE METHOD

• PRACTICE QUESTION:

4. Use Master theorem to give the tight asymptotic bounds of the following
recurrences:
풏
a) 푻 풏 = ퟒ푻 + 풏
ퟐ
풏
b) 푻 풏 = ퟒ푻 + 풏ퟐ
ퟐ

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 127

 TOPIC: TYPES OF DATA STRUCTURES

The Objective of this topic is to make students understand the data types and
types of data structures:

1. DATA TYPES
2. PRIMITIVE AND NON-PRIMITIVE DATA TYPES
3. LINEAR DATA STRUCTURE
4. NON-LINEAR DATA STRUCTURE

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 128

 TOPIC: TYPES OF DATA STRUCTURES

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 129

 TOPIC: TYPES OF DATA STRUCTURES

DATA TYPES: Data Types are declarations of variables. This determines the type
and size of data associated with variables.

TYPES OF DATA STRUCTURES:

1. PRIMITIVE DATA-STRUCTURES

2. NON-PRIMITIVE DATA-STRUCTURES

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 130

 TOPIC: PRIMITIVE DATA STRUCTURES

• PRIMITIVE DATA STRUCTURES:

• Primitive data structure is considered as the fundamental data

structure and it allows storing the values of only one data type.
• The primitive data structure consists of fundamental data types like
float, character, integer, etc.
• A variable with the data type integer can allow storing the values of
integer type only, a variable with the float data type can allow storing
the values of float data type, and the variable with the character data
type allows storing character values only.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 131

 TOPIC: PRIMITIVE DATA STRUCTURES

• PRIMITIVE DATA STRUCTURES:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 132

 TOPIC: PRIMITIVE DATA STRUCTURES

IMAGE SHOWING EIGHT PRIMITIVE DATA TYPES INTO 4 GROUPS

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 133

 TOPIC: NON-PRIMITVE DATA STRUCTURES

• NON-PRIMITIVE DATA STRUCTURES:

• Non-Primitive data structures are considered as the user-defined structure that

allows storing values of different data types within one entity.

• Non-primitive data structures are the data structures created by the programmer
with the help of primitive data structures.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 134

 TOPIC: TYPES OF NON-PRIMITIVE DATA STRUCTURES

• NON-PRIMITIVE DATA STRUCTURES ARE FURTHER DIVIDED INTO TWO

CATEGORIES:

1. LINEAR DATA STRUCTURES

2. NON-LINEAR DATA STRUCTURES

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 135

 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• LINEAR DATA STRUCTURES:

• In linear data structures, the elements are arranged in sequence one
after the other. Since elements are arranged in a particular order,
they are easy to implement. However, when the complexity of the
program increases, the linear data structures might not be the best
choice because of operational complexities.

• Examples: ARRAYS,LINKED LIST, QUEUES, STACKS.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 136

 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• LINEAR DATA STRUCTURES:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 137

 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• NON-LINEAR DATA STRUCTURES:

• Unlike linear data structures, elements in non-linear data structures
are not in any sequence. Instead, they are arranged in a hierarchical
manner where one element will be connected to one or more
elements.

• Examples: TREES, GRAPHS, MAP

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 138

 TOPIC: TYPES OF NON-LINEAR DATA STRUCTURES

• NON-LINEAR DATA STRUCTURES:

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 139

 TOPIC: DIFFERENCE BETWEEN LINEAR AND NON-LINEAR DATA
STRUCTURES
S.NO LINEAR DATASTRUCTURES NON-LINEAR DATA STRUCTURES
1 The data items are arranged in The data items are arranged in non-sequential
sequential order, one after the other. order (hierarchical manner).

2 All the items are present on the single The data items are present at different layers.
layer.

3 It can be traversed on a single run. That It requires multiple runs. That is, if we start from
is, if we start from the first element, we the first element it might not be possible to
can traverse all the elements sequentially traverse all the elements in a single pass.
in a single pass.

4 The memory utilization is not efficient. Different structures utilize memory in different
efficient ways depending on the need.

5 The time complexity increase with the Time complexity remains the same.
data size.

6 Example: Arrays, Stack, Queue. Example: Tree, Graph, Map.

8/20/2025 Prof. Chandrapal Arya BCSE0301 UNIT-I 140
 Youtube & NPTEL Video Links and Online Courses Details
1. https://www.youtube.com/watch?v=zWg7U0OEAoE&list=PLBF3763AF2E1C572F&index=1
2. https://www.youtube.com/watch?v=aGjL7YXI31Q&list=PLEbnTDJUr_IeHYw_sfBOJ6gk5pie0yP-0
3. https://www.youtube.com/watch?v=FEnwM-iDb2g&list=PLEbnTDJUr_IeHYw_sfBOJ6gk5pie0yP-0&index=2
4. https://www.youtube.com/watch?v=HEjmH9wKiMo&list=PLEbnTDJUr_IeHYw_sfBOJ6gk5pie0yP-0&index=6
5. https://www.youtube.com/watch?v=sr_bR1WwcLY
6. https://www.youtube.com/watch?v=puMz5Jt96sg
7. https://www.youtube.com/watch?v=d_XvFOkQz5k&list=PLhb7SOmGNUc5AZurO-im4t_RDr-ymjz0d&index=1
8. https://www.youtube.com/watch?v=KELqVT7hjeE&list=PLhb7SOmGNUc5AZurO-im4t_RDr-ymjz0d&index=2
9. https://www.youtube.com/watch?v=CZYR2v8rYLA&list=PLhb7SOmGNUc5AZurO-im4t_RDr-ymjz0d&index=3
10. https://www.youtube.com/watch?v=-lY4_THb2wM&list=PLhb7SOmGNUc5AZurO-im4t_RDr-ymjz0d&index=4
Th y