Dsa-1 Unit-1

Noida Institute of Engineering and Technology, Greater Noida
INTRODUCTION TO DATA STRUCTURES AND

ALGORITHMS
Unit: 1
SUBJECT NAME:- DATA STRUCTURES AND

ALGORITHMS-I
SUBJECT CODE:- (BCSE 0301) FACULTY NAME: Dr. Megha Gupta
DESIGNATION : Assistant Professor
DEPARTMENT: CSE
COURSE: B.Tech COLLEGE:- NIET, GREATER NOIDA
BRANCH: CSE
SECTION: A,B,C,D
EVALUATION SCHEME
Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

11/17/2024 2
BCSE0301 UNIT1
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.

11/17/2024 3
BCSE0301 UNIT1
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.

11/17/2024 4
BCSE0301 UNIT1
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.

11/17/2024 5
BCSE0301 UNIT1
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 .

11/17/2024 6
BCSE0301 UNIT1
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.

11/17/2024 7
BCSE0301 UNIT1
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.

11/17/2024 8
BCSE0301 UNIT1
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

11/17/2024 9
BCSE0301 UNIT1
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.

11/17/2024 10
BCSE0301 UNIT1
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.

11/17/2024 11
BCSE0301 UNIT1
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.

11/17/2024 12
BCSE0301 UNIT1
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

11/17/2024 13
BCSE0301 UNIT1
COURSE OBJECTIVE
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
EDUCATIONAL PEO’s DESCRIPTION
OBJECTIVES (PEO’s)
To have an excellent scientific and engineering breadth so as to comprehend, analyze, design
PEO1 and provide sustainable solutions for real-life problems using state-of-the-art technologies.
To have a successful career in industries, to pursue higher studies or to support

PEO2 entrepreneurial endeavors and to face the global challenges.
To have an effective communication skills, professional attitude, ethical values and a desire
PEO3 to learn specific knowledge in emerging trends, technologies for research, innovation and
product development and contribution to society.
To have life-long learning for up-skilling and re-skilling for a successful professional career as
PEO4 an engineer, scientist, entrepreneur or bureaucrat for the betterment of the society.
PATTERN OF END SEMESTER EXAMINATION (100 MARKS)
PRE-REQUISITE FOR THE SUBJECT
S.NO TOPIC UNDERSTANDING
PROGRAMMING BASIC UNDERSTANDING OF C AND

1 PYTHON.
ARRAYS CREATION OF ARRAYS

2
POINTERS BASIC UNDERSTANDING OF WORKING
3 WITH POINTERS (C LANGUAGE)
CLASS CREATION OF CLASS AND IT’S OBJECTS.

4
FLOW CHART AND ALGORITHMS BASIC SYMBOLS AND PSEUDO CODE.
5
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.

11/17/2024 31
BCSE0301 UNIT1
INTRODUCTION: WHAT IS DATA STRUCTURES ?

11/17/2024 32
BCSE0301 UNIT1
INTRODUCTION: WHY SHOULD WE LEARN DATA STRUCTURES ?
• PROBLEM SOLVING
• ALGORITHM DESIGN
• REQUIREMENTS FOR THE JOB
• COMPETETIVE PROGRAMMING
• BETTER UNDERSTANDING OF COMPUTER SCIENCE

11/17/2024 33
BCSE0301 UNIT1
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.

11/17/2024 34
BCSE0301 UNIT1
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:

11/17/2024 35
BCSE0301 UNIT1
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

11/17/2024 36
BCSE0301 UNIT1
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

11/17/2024 37
BCSE0301 UNIT1
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.

11/17/2024 38
BCSE0301 UNIT1
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.

11/17/2024 39
BCSE0301 UNIT1
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

11/17/2024 40
BCSE0301 UNIT1
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
11/17/2024 41
BCSE0301 UNIT1
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.

11/17/2024 42
BCSE0301 UNIT1
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
11/17/2024 43
BCSE0301 UNIT1
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

11/17/2024 44
BCSE0301 UNIT1
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.
11/17/2024 45
BCSE0301 UNIT1
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.

11/17/2024 46
BCSE0301 UNIT1
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
11/17/2024 47
Constant
BCSE0301 UNIT1 Time
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

11/17/2024 48
BCSE0301 UNIT1
ALGORITHM EXAMPLE
Algo 1(n)
{
j=1
for(i=1;i<=n;i=i+2)
{
j=j+1
}
}
𝑎. 𝑝
𝑇𝑘 = 𝑎𝑘 + 𝑘 − 1 𝑑

11/17/2024 49
BCSE0301 UNIT1
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
}
}
𝑔. 𝑝 }
𝑇𝑘 = 𝑎. 𝑟 𝑘−1

11/17/2024 50
BCSE0301 UNIT1
ALGORITHM EXAMPLE
Int IsPrime(n)
{
for(i=2;i<= 𝑛;i=i++)
{
if(n%i == 0)
{
print(“not prime”)
return 0;
}
return 1;
}

11/17/2024 51
BCSE0301 UNIT1
Time Complexity for nested loops
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
k = i+j
}
}
print(k)

11/17/2024 52
BCSE0301 UNIT1
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=j+2)
{
k = i+j
}
}
print(k)

11/17/2024 53
BCSE0301 UNIT1
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j=j*2)
{
k = i+j
}
}
print(k)

11/17/2024 54
BCSE0301 UNIT1
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)
11/17/2024 55
BCSE0301 UNIT1
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).

11/17/2024 56
BCSE0301 UNIT1
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.

11/17/2024 57
BCSE0301 UNIT1
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.

11/17/2024 58
BCSE0301 UNIT1
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

11/17/2024 59
BCSE0301 UNIT1
COMMON TIME COMPLEXITIES:

11/17/2024 60
BCSE0301 UNIT1
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.

11/17/2024 61
BCSE0301 UNIT1
1. CONSTANT TIME : O(1)
CONSTANT TIME COMPLEXITY GRAPH

11/17/2024 62
BCSE0301 UNIT1
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))
11/17/2024 63
BCSE0301 UNIT1
2. LINEAR TIME : O(n)
LINEAR TIME COMPLEXITY GRAPH

11/17/2024 64
BCSE0301 UNIT1
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.

11/17/2024 65
BCSE0301 UNIT1
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.

11/17/2024 66
BCSE0301 UNIT1
LOGARITHMIC TIME COMPLEXITY GRAPH

11/17/2024 67
BCSE0301 UNIT1
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).

11/17/2024 68
BCSE0301 UNIT1
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)

11/17/2024 69
BCSE0301 UNIT1
5. QUADRATIC TIME: O(n^2)
QUADRATIC TIME COMPLEXITY GRAPH

11/17/2024 70
BCSE0301 UNIT1
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)

11/17/2024 71
BCSE0301 UNIT1
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.

11/17/2024 72
BCSE0301 UNIT1
BIG-O Complexity Chart:

11/17/2024 73
BCSE0301 UNIT1
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

11/17/2024 74
BCSE0301 UNIT1
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).

11/17/2024 75
BCSE0301 UNIT1
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

11/17/2024 76
BCSE0301 UNIT1
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.

11/17/2024 77
BCSE0301 UNIT1
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

11/17/2024 78
BCSE0301 UNIT1
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.

11/17/2024 79
BCSE0301 UNIT1
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)).

11/17/2024 80
BCSE0301 UNIT1
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))

Dr. Megha Gupta DATA STRUCTURES AND
11/17/2024 81
ALGORITHMS-I BCSE0301 UNIT1
• 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)

11/17/2024 82
BCSE0301 UNIT1
• 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)

11/17/2024 83
BCSE0301 UNIT1
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.

11/17/2024 84
BCSE0301 UNIT1
• 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))

11/17/2024 85
BCSE0301 UNIT1
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)

11/17/2024 86
BCSE0301 UNIT1
• Q1 f(n) = 3n + 4, g(n) = n, Prove f(n) = Ω (g(n))
• Q2 f(n) = 𝑛, g(n) = log 2 𝑛, Prove f(n) = Ω (g(n))

11/17/2024 87
BCSE0301 UNIT1
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.

11/17/2024 88
BCSE0301 UNIT1
• 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))

11/17/2024 89
BCSE0301 UNIT1
• Q1 f(n) = 10𝑛2 𝑙𝑜𝑔2 𝑛 + 3n + 4, g(n) = 𝑛2 𝑙𝑜𝑔2 𝑛 , Prove f(n) = θ(g(n))

11/17/2024 90
BCSE0301 UNIT1

11/17/2024 91
BCSE0301 UNIT1
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 n 0 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
Dr. Megha Gupta DATA STRUCTURES AND

11/17/2024 92
ALGORITHMS-I BCSE0301 UNIT1
Another Definition for o notation.
f(n) = o(g(n)) if and only if Q Justify n! = o(𝑛𝑛 )
𝑓(𝑛)
lim =0
𝑛→∞ 𝑔(𝑛)

11/17/2024 93
BCSE0301 UNIT1
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 n 0 such that
f(n) > c*g(n)>=0 for all n >= n 0}
• Another definition for o notation:

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

11/17/2024 94
BCSE0301 UNIT1
Another Definition for w notation.
f(n) = w(g(n)) if and only if
𝑔(𝑛)
lim =0
𝑛→∞ 𝑓(𝑛)

11/17/2024 95
BCSE0301 UNIT1
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.

11/17/2024 96
BCSE0301 UNIT1
• 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

11/17/2024 97
BCSE0301 UNIT1
• 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 = 0 and if n=1 then 𝑓1 = 1 . These
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”.

11/17/2024 98
BCSE0301 UNIT1
• 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 = 0 and if n=1 then 𝑓1 = 1 . These
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
11/17/2024 99
BCSE0301 UNIT1
• 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)
𝑒𝑛𝑑𝑖𝑓

11/17/2024 100
BCSE0301 UNIT1
• 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)

11/17/2024 101
BCSE0301 UNIT1
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

11/17/2024 102
BCSE0301 UNIT1
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.

11/17/2024 103
BCSE0301 UNIT1
• 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.

11/17/2024 104
BCSE0301 UNIT1
• 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.

11/17/2024 105
BCSE0301 UNIT1

11/17/2024 106
BCSE0301 UNIT1
• 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!

11/17/2024 107
BCSE0301 UNIT1
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.

11/17/2024 108
BCSE0301 UNIT1
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.

11/17/2024 109
BCSE0301 UNIT1
The Recursion tree method is especially used to solve a recurrence of

the form:
𝒏
𝑻 𝒏 = 𝒂𝑻 + 𝒏
𝒃
where a>1, b≥1

11/17/2024 110
BCSE0301 UNIT1
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:

11/17/2024 111
BCSE0301 UNIT1
𝒏
• 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:

11/17/2024 112
BCSE0301 UNIT1

11/17/2024 113
BCSE0301 UNIT1
• 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”.

11/17/2024 114
BCSE0301 UNIT1
𝒏
• 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:

11/17/2024 115
BCSE0301 UNIT1

11/17/2024 116
BCSE0301 UNIT1
𝒏
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:

11/17/2024 117
BCSE0301 UNIT1

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

11/17/2024 119
BCSE0301 UNIT1
• 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.”

11/17/2024 120
BCSE0301 UNIT1
• 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
=𝒏𝒍𝒐𝒈𝟐 𝒏

11/17/2024 121
BCSE0301 UNIT1
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).

11/17/2024 122
BCSE0301 UNIT1
• 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
sufficiently large 𝒏. 𝑻 𝒏 = 𝜽(𝒇 𝒏 )

11/17/2024 123
BCSE0301 UNIT1
• 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.)

11/17/2024 124
BCSE0301 UNIT1
𝑛
• Example 1:Consider the recurrence of 𝑇 𝑛 = 9𝑇 + 𝑛in which a=9,
3𝒂−𝒆
b=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 𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏𝑎 . 𝑙𝑜𝑔𝑛) = Θ(𝑙𝑜𝑔𝑛).

11/17/2024 125
BCSE0301 UNIT1
• 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:
𝒏
a) 𝑻 𝒏 = 𝟒𝑻 𝟐
+𝒏
𝒏 𝒏 𝒏
b) 𝑻 𝒏 = 𝑻 𝟐
+𝑻
𝟒
+𝑻
𝟖
+𝒏

11/17/2024 126
BCSE0301 UNIT1
• PRACTICE QUESTION:
4. Use Master theorem to give the tight asymptotic bounds of the following
recurrences:
𝒏
a) 𝑻 𝒏 = 𝟒𝑻 𝟐
+𝒏
𝒏
b) 𝑻 𝒏 = 𝟒𝑻 + 𝒏𝟐
𝟐

11/17/2024 127
BCSE0301 UNIT1
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

11/17/2024 128
BCSE0301 UNIT1

11/17/2024 129
BCSE0301 UNIT1
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

11/17/2024 130
BCSE0301 UNIT1
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.

11/17/2024 131
BCSE0301 UNIT1
• PRIMITIVE DATA STRUCTURES:

11/17/2024 132
BCSE0301 UNIT1
IMAGE SHOWING EIGHT PRIMITIVE DATA TYPES INTO 4 GROUPS

11/17/2024 133
BCSE0301 UNIT1
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.

11/17/2024 134
BCSE0301 UNIT1
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

11/17/2024 135
BCSE0301 UNIT1
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.

11/17/2024 136
BCSE0301 UNIT1
• LINEAR DATA STRUCTURES:

11/17/2024 137
BCSE0301 UNIT1
• 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

11/17/2024 138
BCSE0301 UNIT1
• NON-LINEAR DATA STRUCTURES:

11/17/2024 139
BCSE0301 UNIT1
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, Dr.

Stack,
MeghaQueue.
Gupta DATA STRUCTURESExample: Tree, Graph, Map.
AND ALGORITHMS-I
11/17/2024 140
BCSE0301 UNIT1
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
Thank you

Dsa-1 Unit-1

Uploaded by

Copyright:

Available Formats

Dsa-1 Unit-1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dsa-1 Unit-1

Uploaded by

Copyright:

Available Formats

Noida Institute of Engineering and Technology, Greater Noida

INTRODUCTION TO DATA STRUCTURES AND

SUBJECT NAME:- DATA STRUCTURES AND

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

Algorithms, Analyzing Algorithms, Complexity of

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

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

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

OPTIMIZATION: Enhancing DATABASE MANAGEMENT: Use data

OPERATING SYSTEM: Implementation

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

MACHINE LEARNING: Use of algorithms NATURE LANGUAGE PROCESSING:

SEARCH ALGORITHMS: Implementing PATTERN RECOGNISTION: Efficiently

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

REINFORCEMENT LEARNING: Algorithms like

COMPUTER SCIENCE AND

MODEL EVALUATION: Algorithms for cross-

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

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

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

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

SENSOR DATA PROCESSING: Algorithms NETWORK PROTOCOLS: Design and

SECURITY: Implementing algorithms for

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

INTRUSION DETECTION: Use of data structures

COMPUTER SCIENCE AND

NETWORK SECURITY: Implement and analyze

Dr. Megha Gupta DATA STRUCTURES AND ALGORITHMS-I

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.

with the help of fundamental data structures.

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

Engineering Graduates will be able to:

PO2 : Problem Analysis

PO3 : Design/Development of solutions

PO4 : Conduct Investigations of complex problems

PO5 : Modern tool usage

PO6 : The engineer and society

Engineering Graduates will be able to:

PO9 : Individual and teamwork

PO11 : Project management and finance

PO12 : Life-long learning

Sr. No Course Outcome

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

S.NO PROGRAM SPECIFIC PSO DESCRIPTION

PSO1 PSO2 PSO3 PSO4

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

S.NO TOPIC UNDERSTANDING

PROGRAMMING BASIC UNDERSTANDING OF C AND

ARRAYS CREATION OF ARRAYS

CLASS CREATION OF CLASS AND IT’S OBJECTS.

Above Links will give you a brief reference of Subject.

11 TYPES OF DATA STRUCTURES:

• What is Data Structures?

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