Data Structures,Unit-1 (Notes prepared by Dr.

11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Data Structures

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 1

Pre-Requisites & Course Outcomes

• Pre-requisites:
1. Basic knowledge of one programming language (C, C++, C#, Java, JavaScript,
Python2/3, Ruby, Scala)
2. Basic knowledge of common programming concepts, including control structures,
loops, and recursion
3. Basic knowledge of mathematics, including proof by induction and contradiction
• Course Outcomes (Cos):
1. To provide the knowledge of basic data structures and their implementations.
2. To understand importance of data structures in context of writing efficient
programs.
3. To develop skills to apply appropriate data structures in problem solving.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 2

Syllabus – Unit 1
Introduction to
Algorithms and Data structures
Concepts and design of algorithm ,Various notations used in
representing complexities of algorithms, Introduction to data structures
and their utilities Types of data structures ,Data structure operation

Number of Applicable Total Hours (L+T+P+S) (6+0+6+3)= 15

• Books
1. Data structures using C E Balaguruswami
2. Data Structures and Algorithms Made Easy by Narasimha Karumanchi
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 3

1
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Introduction

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY
SYMBIOSIS
OF APPLIED
UNIVERSITY
SCIENCES,
OFINDORE
APPLIEDBy
SCIENCES,
Dr. Vaishali
INDORE
Joshi By Dr. Vaishali Joshi 4

Concepts and Design of Algorithm

• Why do we use Algorithm?

1. Benefit of Algorithm
• Easy to understand.
• Logic is developed before actual coding.
2. Benefit of Analysis of Algorithm
• To find best version of solution from various solutions of same problem.
3. Benefit of Design of Algorithm
1. To create an efficient algorithm to solve a problem in an efficient way.

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 5

Algorithm: Definition

• An algorithm is any well-defined procedure that takes some values as

input and produces some values as output.

Input Output
Algorithm

• An algorithm is thus a finite sequence of computational steps that

transforms
**Study the
material prepared by input
Dr. Vaishali Joshi into desired output in finite amount of time.
SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 6

2
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Algorithm for Problem Solving

• Problem definition
• What task has to be done.
• Calculation of mean, square root, shortest path etc.
• Algorithm design
• Writing pseudo code, drawing flow chart etc. (Decision of algorithm design model like Divide
& Conquer, Dynamic Programming, Greedy etc.)
• Algorithm analysis
• Analysis of time and space required to run the algorithm.
• Implementation
• Writing a program
• Testing
• Testing of the output
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 7

Properties of Algorithm

• Finiteness: An algorithm must terminate after a finite number of steps.

• Absence of Ambiguity: Each instruction must be clear and unambiguous.
• Definition of Sequence: Each step must have a unique defined preceding and
succeeding step. The first step (start) and last step (halt) must be clearly noted.
• Input / Output: Number and types of required inputs and results must be
specified
• Feasibility: It must be possible to perform each instruction

Note: A procedure that has all the characteristics of an algorithm except finiteness is called
**Study material prepared by Dr. Vaishali Joshi
computational methods.
SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 8

Characteristics of Algorithm
• Input: An algorithm has zero or more input
• Output: An algorithm has one or more output.
• Definiteness: Each instruction must be clear and unambiguous.
• Effectiveness: An algorithm must be effective in such a way that its
operations are sufficiently basic and feasible.
• Termination: It must terminate with the production of correct output
from the given input
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 9

3
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Example of an Algorithm

• Problem: To find the max element of an array

Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
Max ←A[0]
for i ←1 to n-1 do
if A[i] > Max then
Max ← A[i]
End For
return Max
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 10

Algorithm Design Techniques

• Several popular design approaches are:

1. Divide-and-Conquer (D and C)
2. Branch-and-Bound
3. Greedy Approach
4. Randomized Algorithms
5. Dynamic Programming
6. Backtracking Algorithms

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 11

Algorithm analysis

The goal of the analysis of algorithms is to compare algorithms (or

solutions) mainly in terms of running time but also in terms of other
factors (e.g., memory, developer effort, etc.). Why do we analyse the
algorithm?
• To decide the better algorithm among various solutions of a given problem.
• For example, better algorithm among all sorting algorithm
• Suppose you have written an algorithm for a given problem and the solution of the
problem already exists. How do you prove your algorithm is better?
• To check feasibility
• Even if the solution is given first time of any given problem, the analysis of an algorithm
can decide whether the algorithm will run with feasible recourse (Time and Space)
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 12

4
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Algorithm analysis: Factors to analyze

• Time

• Space

• Correctness of an algorithm

• Communication time [For network solution]

• Power consumption [For Mobile App]

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 13

Algorithm Analysis

Priori Analysis Posteriori analysis

Analysis is done before the real implementation Analysis is done after the real implementation of
of algorithm algorithm i.e. program
Priori analysis is an absolute analysis. Posteriori analysis is a relative analysis.
Independent on the hardware and compiler Dependent on the hardware and compiler
It gives approximate answer It gives exact answer
The complexity remains same for every system The complexity differs from system to system

Asymptotic notations are used to represent the Complexity is represented in terms of watch
complexity in terms of time and space functions time ( milli second, nano second etc.) and
**Study material prepared by Dr. Vaishali Joshi
bits/bytes (for space complexity)
SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 14

Algorithm Analysis

• Algorithm Analysis involves mainly two types of analysis

• Time complexity: The amount of time required to run an algorithm.

• Space complexity: The amount of memory space required to run an

algorithm.

Algorithm analysis

Time Complexity Space Complexity

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 15

5
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

How to calculate running time of an

algorithm?
1. We can calculate the running time of an algorithm reliably by
running the implementation of the algorithm on a computer.
2. Alternatively, we can calculate the running time by using a
technique called Algorithm Analysis.
3. We can estimate’s an algorithm’s performance by counting the
number of basic operations required by the algorithm to process an
input of a certain size.

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 16

Algorithm Analysis: Time Analysis

• Time complexity of an algorithm can be analysed by following way.

• Consider each basic step of algorithm takes 1 unit of time.

• Count the frequency of the each step

Then, the time complexity of the algorithm, T(n), will be

T(n)= 1* fS1 + 1* fS2 +1* fS3 ………..+1* fSn
Where,
fSn = frequency of step n

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 17

Algorithm Analysis: Time Analysis

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 18

6
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Space Complexity
• Space complexity of an algorithm represents the amount of memory
space needed by the algorithm in its life cycle.
• The space complexity of an algorithm or a computer program is the
amount of memory space required to solve an instance of
the computational problem as a function of characteristics of the
input. It is the memory required by an algorithm until it executes
completely.
• Space needed by an algorithm is equal to the sum of the following
two components – Fixed and variable
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 19

Space Complexity
• A fixed part that is a space required to store certain data and
variables (i.e. simple variables and constants, program size etc.), that
are not dependent of the size of the problem.
• A variable part is a space required by variables, whose size is totally
dependent on the size of the problem. For example, recursion stack
space, dynamic memory allocation etc.
• Space complexity S(p) of any algorithm p is S(p) = A + S(I) Where A is
treated as the fixed part and S(I) is treated as the variable part of the
algorithm which depends on instance characteristic I.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 20

Space Complexity

Following is a simple example that tries to explain the concept

SUM (P, Q)
Step -1: START
Step -2: R  P + Q + 10
Step -1: STOP

Here we have three variables P, Q and R and one constant. Hence S(p) =
1+3. Now space is dependent on data types of given constant types and
variables and it will be multiplied accordingly.

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 21

7
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Space Complexity
Auxiliary space: Space other than that consumed by the input.
We often speak of Auxiliary space (extra memory) needed, not counting the memory
needed to store the input itself.
Example:
int FindMax(int A[], int n)
{
int max=A[0];
for (int i=0;i<n;i++){
if(A[i]>max)
max=A[i];
}
return max;
}
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 22

Algorithm Analysis: Order of growth

• In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input
size (we don’t measure the actual running time). We calculate, how the time (or space)
taken by an algorithm increases with the input size.
• The rate at which the running time increases as a function of input is called rate of
growth.
• Order of growth (or Growth Rate) of an algorithm predicts that how execution time or
space of an algorithm changes with the input size.
• Let's understand with an example,

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 23

Algorithm Analysis: Order of growth

• Observations:
• At n=10, Algorithm A looks bad.
• As n increases, the Algorithm A looks
better. (Why?)
• Regardless of the coefficients, there
will always be some value of n where an2 > bn.
• Even if the run time of Algorithm A were n + 10000, it would still be better
than Algorithm B for sufficiently large n.
• Conclusion: The coefficient and non-leading term do not affect the
order of growth for some sufficient large value of n.
The leading term is the term with the highest exponent.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 24

8
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Commonly Used Rates of Growth

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 25

Algorithm Analysis: Asymptotic notation

• Asymptotic notations are mathematical tools to represent the time

complexity of algorithms for asymptotic analysis.
• The Asymptotic notations are used to describe the rate of growth of
functions.
• Asymptotic notation is a way to describe the running time or space
complexity of an algorithm based on the input size. It is commonly
used in complexity analysis to describe how an algorithm performs as
the size of the input grows.

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 26

Algorithm Analysis: Asymptotic notation

The three most commonly used notations are Big O, Omega, and Theta.
• Big O notation (O): This notation provides an upper bound on the growth
rate of an algorithm’s running time or space usage. It represents the worst-
case scenario, i.e., the maximum amount of time or space an algorithm
may need to solve a problem. For example, if an algorithm’s running time is
O(n), then it means that the running time of the algorithm increases
linearly with the input size n or less.
• Omega notation (Ω): This notation provides a lower bound on the growth
rate of an algorithm’s running time or space usage. It represents the best-
case scenario, i.e., the minimum amount of time or space an algorithm
may need to solve a problem. For example, if an algorithm’s running time is
Ω(n), then it means that the running time of the algorithm increases
linearly with the input size n or more.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 27

9
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Algorithm Analysis: Asymptotic notation

• Theta notation (Θ): This notation provides both an upper and lower
bound on the growth rate of an algorithm’s running time or space
usage. It represents the average-case scenario, i.e., the amount of
time or space an algorithm typically needs to solve a problem. For
example, if an algorithm’s running time is Θ(n), then it means that the
running time of the algorithm increases linearly with the input size n.
It is important to note that asymptotic notation does not provide an
exact running time or space usage for an algorithm, but rather a
description of how the algorithm scales with respect to input size. It is a
useful tool for comparing the efficiency of different algorithms and for
predicting how they will perform on large input sizes.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 28

Algorithm Analysis: Asymptotic notation

Following are the types of asymptotic notations, we generally use.

1. Big–OH (O)

2. Big–OMEGA (Ω)

3. Big–THETA (Θ)

4. Little–OH (o)

5. Little–OMEGA (ω)

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 29

Asymptotic notation: Big–OH (O)

• Let f(n) and g(n) be two functions from set of integers to real
numbers , f:Z→R, then f(n) is O(g(n)) or f(n) = O(g(n)) iff
0≤𝑓 𝑛 ≤𝐶∗𝑔 𝑛 ∀𝑛 ≥ 𝑛0
Where, C and n0 are any positive real constants Big Oh notation
always gives
Upper Bound

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 30

10
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Asymptotic notation: Big–OH (O)

• Let f(n)= n3+3n+5 then

• f(n)=O(n3) True/ False
• f(n)=O(n) True/ False
• f(n)=O(n4) True/ False
• f(n)=O(nlogn) True/ False
• f(n)=O(n3logn) True/ False
• f(n)=O(n3logn)
**Study material prepared by Dr. Vaishali Joshi True/ False
SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 31

Asymptotic notation: Big–OH (O)

• Let f(n)= n3+3n+5 and g(n)= n3. If f(n)=O(g(n)) then find C and n0.

Let f(n)=n2+3n+5. if f(n)=O(g(n)) then what could be the possible values for
g(n)?

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 32

Asymptotic notation: Big–Omega (Ω)

• Let f(n) and g(n) be two functions from set of integers to real numbers , f:Z→R, then
f(n) is Ω(g(n)) or f(n) = Ω(g(n)) iff
0 ≤ 𝐶 ∗ 𝑔 𝑛 ≤ 𝑓(𝑛) ∀𝑛 ≥ 𝑛0
Where, C and n0 are any positive real constants Big Omega
notation always
gives Lower Bound

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 33

11
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Asymptotic notation: Big–Omega (Ω)

• Let f(n)= n3+3n+5 then

• f(n)=Ω (n3) True/ False
• f(n)= Ω(n) True/ False
• f(n)= Ω(n4) True/ False
• f(n)= Ω(nlogn) True/ False
• f(n)= Ω(logn) True/ False
• f(n)= Ω(n2logn)
**Study material prepared by Dr. Vaishali Joshi True/ False
SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 34

Asymptotic notation: Big–Omega (Ω)

• Let f(n)= n+5 and f(n) ∈ Ω (n). Calculate C and n0.

• Let f(n)=n2+3n+5. if f(n)=Ω (g(n)) then what could be the possible

values for g(n)?
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 35

Asymptotic notation: Big–Theta (Θ)

• Let f(n) and g(n) be two functions from set of integers to real
numbers , f:Z→R, then f(n) is Θ (g(n)) or f(n) = Θ (g(n)) iff
0 ≤ 𝐶1 ∗ 𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝐶2 ∗ 𝑔(𝑛) ∀𝑛 ≥ 𝑛0
Where, C and n0 are any positive real constants Big Theta notation
always gives tight
bound

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 36

12
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Asymptotic notation: Big–Theta (Θ)

• Let f(n)= n3+3n+5 then

• f(n)=Θ (n3) True/ False
• f(n)= Θ (n) True/ False
• f(n)= Θ (n4) True/ False
• f(n)= Θ (nlogn) True/ False
• f(n)= Θ (logn) True/ False
• f(n)= Θ (n2logn)
**Study material prepared by Dr. Vaishali Joshi True/ False
SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 37

Asymptotic notation: Big–Theta (Θ)

• Let f(n)= n+5 and f(n) ∈ Θ (n). Calculate C1, C2 and n0.

• Let f(n)=n2+3n+5. if f(n)=Θ (g(n)) then what could be the possible

value(s) for g(n)?
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 38

Asymptotic notation: Big–Theta (Θ)

• Sometimes, we can not express the function in tight bound

• For example, Let f(n)=n!
We know that n!=1*2*3*……*(n-1)*n
Hence,
1 ≤ 1∗2∗3 … … ∗ 𝑛 − 1 ∗ 𝑛 ≤ 𝑛 ∗ 𝑛 ∗ 𝑛 ∗ ⋯ ∗ 𝑛
1 ≤ 𝑛! ≤ 𝑛
Here, f(n)=O(𝑛 ) and f(n)=Ω(1). But no theta bound.
Same you can find for f(n)=logn!
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 39

13
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Asymptotic notations: O, Θ and Ω

1 < 𝑙𝑜𝑔𝑛 < 𝑛 < 𝑛 < 𝑛𝑙𝑜𝑔𝑛 < 𝑛 < 𝑛 … … . < 2 < 3 … … .
< 𝑛

Lower Bound Upper Bound

Tight Bound
or
Average bound

Let f(n)=n2+5 then f(n)=O(n2) (How?) and f(n)=Ω (n2) (How?) that implies f(n)=
Θ (n2).
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 40

Asymptotic notations: O, Θ and Ω

• Let f(n) and g(n) be two functions, from set of integers to real numbers , f:Z→R,
such that
𝑓(𝑛)
lim =𝐴
→ 𝑔(𝑛)
then,
if A=0 then f(n)=O(g(n)) but f(n) ≠ Θ (g(n))
if A=∞ then f(n)=Ω (g(n)) but f(n) ≠ Θ (g(n))
if A≠0 and A is finite f(n) = Θ (g(n))
Ponder: Can we compare order of growth from above statements?
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 41

Asymptotic notations: Little-OH (o)

• Let f(n) and g(n) be two functions, from set of integers to real numbers , f:Z→R, then
f(n) is o(n) or f(n) ∈ o(n) iff
0≤𝑓 𝑛 <𝑐∗𝑔 𝑛 ∀𝑛 ≥ 𝑛

Where, C1 and n0 is any positive constant.

Mathematically, if
𝑓(𝑛)
lim =0
→ 𝑔(𝑛)

Then, we can say that f(n)=o(g(n)).

If f(n)=o(g(n)) then f(n)=O(g(n))? And if f(n)=O(g(n)) then f(n)=o(g(n))?
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 42

14
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Asymptotic notations: Little-Omega(ω)

• Let f(n) and g(n) be two functions, , from set of integers to real numbers , f:Z→R, then
f(n) = ω(n) or f(n) ∈ ω (n) iff
𝑓 𝑛 >𝑐∗𝑔 𝑛 ≥0 ∀𝑛 ≥ 𝑛

Where, C1 and n0 is any positive constant.

Mathematically, if
𝑓(𝑛)
lim =∞
→ 𝑔(𝑛)

Then, we can say that f(n)=ω (g(n)).

If f(n)=ω (g(n)) then f(n)= Ω(g(n))? And if f(n)= Ω(g(n)) then f(n)=ω (g(n))?
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 43

Asymptotic notations: Relationship

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 44

Introduction to Data Structures

Variable
A variable is an abstract storage location paired with an associated symbolic name, which
contains some known or unknown quantity of data or object referred to as a value; or in
simpler terms, it is a placeholder for representing data.
Data Type
In software programming, data type refers to the type of value a variable has and what type of
mathematical, relational or logical operations can be applied without causing an error.
Computer memory is all filled with zeros and ones. If we have a problem and we want to code
it, it’s very difficult to provide the solution in terms of zeros and ones. To help users,
programming languages and compilers provide us with data types. A data type reduces the
coding effort. Examples of data types are: integer, floating point, unit number, character, string,
etc.
At the top level, there are two types of data types:
• System-defined data types (also called Primitive data types)
• User-defined data types
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 45

15
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Introduction to Data Structures

Data structure is a particular way of storing and organizing data in a
computer so that it can be used efficiently. A data structure is a special
format for organizing and storing data.
General data structure types include arrays, files, linked lists, stacks, queues,
trees, graphs and so on.
Depending on the organization of the elements, data structures are classified
into two types:
1. Linear data structures: Elements are accessed in a sequential order but it is not
compulsory to store all elements sequentially. Examples: Linked Lists, Stacks and
Queues.
2. Non – linear data structures: Elements of this data structure are stored/accessed
in aprepared
**Study material non-linear order.
by Dr. Vaishali Joshi Examples: Trees and graphs.

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 46

Introduction to Data Structures

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 47

Abstract Data Types (ADTs)

Abstract Data Types (ADTs)
• All primitive data types (int, float, etc.) support basic operations such
as addition and subtraction. The system provides the
implementations for the primitive data types.
• For user-defined data types we also need to define operations. The
implementation for these operations can be done when we want to
actually use them. That means, user defined data types are defined
along with their operations.
• We combine the data structures with their operations and we call this
Abstract Data Types (ADTs). An ADT consists of two parts:
• Declaration of data
• Declaration of operations
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 48

16
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Abstract Data Types (ADTs)

Abstract Data Types (ADTs)
We combine the data structures with their operations and we call this Abstract
Data Types (ADTs). An ADT consists of two parts:
• Declaration of data
• Declaration of operations

Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues, Binary
Trees, Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, and many
others.

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 49

Applications of Data Structures

Data structures are used in various fields such as:
• Operating system
• Graphics
• Computer Design
• Blockchain
• Genetics
• Image Processing
• Simulation

**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 50

Data Structure Operations

Different operations are supported by various data structures and the expenses for
these operations can be estimated in terms of time complexity, or space
complexity.

Common Data Structure Operations:

1. Access/Search:
Description: Finding the location of a particular element in the data structure.
Examples: Searching for an element in an array, finding a key in a hash table.
2. Insertion:
Description: Adding a new element to the data structure.
Examples: Inserting a node into a linked list, adding an element to an array.
3. Deletion:
Description: Removing an element from the data structure.
Examples: Deleting a node from a linked list, removing an element from an array.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 51

17
Data Structures,Unit-1 (Notes prepared by Dr. 11-01-2025
Vaishali Joshi, Associate Professor – SCSIT,
SUAS, Indore)

Data Structure Operations

4. Traversal:
Description: Visiting and processing each element in the data structure.
Examples: Iterating through elements in an array, traversing nodes in a tree.
5. Sorting:
Description: Arranging elements in a specified order.
Examples: Sorting an array using algorithms like quicksort or mergesort.
6. Merging:
Description: Combining two data structures into one.
Examples: Merging two sorted arrays or merging two sorted linked lists.
7. Splitting:
Description: Dividing a data structure into multiple parts.
Examples: Splitting an array into two halves or splitting a linked list.
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 52

Topics We Have Learned So Far

• Notion of Algorithm
• Properties of Algorithm
• Importance of Analysis of Algorithm
• Time and Space Complexities
• Asymptotic Notations (O,Ɵ,Ω,o, and ω)
• Variables and Data Types
• Introduction to Data Structures & their utilization
• Abstract Data type
• Data Structure Operations
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 53

Thank you

Doubts??
**Study material prepared by Dr. Vaishali Joshi

SYMBIOSIS UNIVERSITY OF APPLIED SCIENCES, INDORE By Dr. Vaishali Joshi 54

18