Dsa(unit 1

continue)
Data structure
Data structures manage how data is stored and accessed, while Algorithms focus on processing
this data. The logical and mathematical order of a particular organization of data is called data
structure. Examples of data structures are Array, Linked List, Tree and Heap, and examples of
algorithms are Binary Search, Quick Sort and Merge Sort.
Key points:
❑ The choice of particular data model is depended upon the concentration.
❑ It must be rich enough to mirror the actual relationships of data in real world.
❑ It should be simple enough that one can access when its necessary.
Let's look at different data structures that are used in different situations.

#linear data structure

➢ Arrays
 An array is a linear data structure and it is a collection of element of same data type stored
at contiguous memory locations.
➢ Linked list
A linked list is a linear data structure in which elements are not stored at contiguous memory
locations. The elements in a linked list are linked using pointers as shown in the below image.

➢ Pointers
Pointers are the variables that store the memory address of another variable. these are used to:-
o Create dynamic data structure.
o Efficient memory usage.
o Implement relationship between data structure.
➢ Stack
Stack is a linear data structure that follows LIFO(Last in first out) principle i.e., entering and retrieving
data is possible from only one end. The entering and retrieving of data is also called push and pop
operation in a stack.

➢ Queue Data Structure

Queue is a linear data structure that follows First In First Out(FIFO) principle i.e. the data item stored
first will be accessed first. In this, entering is done from one end and retrieving data is done from other
end. An example of a queue is any queue of consumers for a resource where the consumer that came
first is served first.
The insertion and deletion operations are enqueue AND dequeue respectively.
#non linear data structure
➢ Tree
A tree is a non-linear and hierarchical data structure where the elements are arranged in a tree-like
structure. In a tree, the topmost node is called the root node. Each node contains some data, and data
can be of any type.
➢ Graph
A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite
set of vertices and set of edges that connect a pair of nodes. The graph is used to solve the most
challenging and complex programming problems. It consist of vertex and edges.

#Operations on different Data Structure:

There are different types of operations that can be performed for the manipulation of data in every data
structure. Some operations are explained and illustrated below:
 Traversing: Traversing a Data Structure means to visit the element stored in it. It visits every element of
data for atleast one time for some processing in a systematic manner.
Insertion: It is the operation which we apply on all the data-structures. Insertion means to add an
element in the given data structure. The operation of insertion is successful when the required element
is added to the required data-structure. It is unsuccessful in some cases when the size of the data
structure is full and when there is no space in the data-structure to add any additional element. The
insertion has the same name as an insertion in the data-structure as an array, linked-list, graph, tree. In
stack, this operation is called Push.
Deletion: It is the operation which we apply on all the data-structures. Deletion means to delete an
element in the given data structure. The operation of deletion is successful when the required element is
deleted from the data structure. The deletion has the same name as a deletion in the data-structure as
an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is
called Dequeue.
Deletion: It is the operation which we apply on all the data-structures. Deletion means to delete an
element in the given data structure. The operation of deletion is successful when the required element is
deleted from the data structure. The deletion has the same name as a deletion in the data-structure as
an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is
called Dequeue.
What is an Algorithm?

 • Step-by-step procedure to solve a problem

 • Takes input and produces output
 • Independent of programming language
Characteristics of an Algorithm

 • Input: Zero or more inputs

 • Output: At least one output
 • Definiteness: Clear and unambiguous steps
 • Finiteness: Terminates after finite steps
 • Effectiveness: Basic, executable operations
Rules to Write an Algorithm

 • Start and End clearly defined

 • Steps written sequentially
 • Use simple language
 • Avoid implementation details
 • Ensure correctness and efficiency
Concept of Algorithm Analysis

 Measures performance of algorithms

 • Evaluates time and space requirements
 • Independent of hardware and language
 • Compares multiple algorithms
Efficient Algorithms

 • Requires less time and memory

 • Scales well with input size
 • Uses optimal logic or data structures
 • Example: Binary Search vs Linear Search
Average Case and Worst Case Analysis

 • Best Case: Minimum time taken

 • Average Case: Expected time
 • Worst Case: Maximum time taken
 • Worst case most commonly used
Asymptotic Analysis

 • Studies algorithm behavior for large input

 • Ignores constants and lower order terms
 • Focuses on growth rate
Big O Notation – O

 • Represents upper bound

 • Describes worst-case complexity
 • Examples: O(1), O(n), O(n²)
Omega Notation – Ω

 • Represents lower bound

 • Describes best-case complexity
 • Ω(n) means algorithm takes at least n time
Theta Notation – Θ

 • Represents tight bound

 • Best and worst case are same
 • Example: Θ(n log n)
What is an Algorithm?
The word Algorithm means "A set of finite rules or instructions to be followed in calculations or
other problem-solving operations" Or "A procedure for solving a mathematical problem in a finite
number of steps that frequently involves recursive operations".
Mainly there are three possible cases of any algorithm which can be analyzed with the help of
complexity:
1. Space Complexity
2. Time Complexity
 Best case:-
When there is wide range of possible runtime for a sequential search algorithm , if the first
integer in the array could have value item so in one examine we achieve our target and it can be
said that this is the best case of algorithm because it is not possible for sequential search or look
at less than one value. example:-
Searching for 5 in the array [ 5 , 2 , 8 , 1 , 9 ] . The algorithm finds 5 immediately.
Time complexity:-o (1)
 Average case:-
In the average case we expect the algorithm to go half width of the array so the complexity of the
array will be f(n) = n/2. example:-
Searching for 5 in the array [ 5 , 2 , 8 , 1 , 9 ] . The algorithm checks 5 , then 2 and then find 8 at the
third position.
Time complexity:-o (n/2)
 Worst case:-
In this last position will contain the item or the item may not be present in the array. So this type of
case is called worst case. example:-
Searching for 9 in the array [ 5 , 2 , 8 , 1 , 9 ] . The algorithm finds 9 in the end after checking each
element present in the array.
Time complexity:-o (n)
Difference between data type and data
structure.
Data Types Data Structures
Data Type is the kind or form of a variable which is Data Structure is the collection of different kinds of
being used throughout the program. It defines that data. That entire data can be represented using an
the particular variable will assign the values of the object and can be used throughout the entire
given data type only program.
Implementation through Data Types is a form of Implementation through Data Structures is called
abstract implementation concrete implementation
Can hold different kind and types of data within one
Can hold values and not data, so it is data less
single object
The data is assigned to the data structure object
Values can directly be assigned to the data type
using some set of algorithms and operations like
variables
push, pop and so on.
Time complexity comes into play when working with
No problem of time complexity
data structures
Asymptotic notations

There are mainly three asymptotic notations :-

Big-o notation ( o-notation) =worst case
Omega notation (Ω-notation) = for best case
Theta notation (Θ- notation) = for average case
➢ Big-O Notation (O-notation):
 If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
 It returns the highest possible output value (big-O)for a given input.
 The execution time serves as an upper bound on the algorithm's time complexity.
Mathematical Representation of Big-O Notation:
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
➢ Omega Notation (Ω-Notation):
Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
Let g and f be the function from the set of natural numbers to itself. The function f is said to be
Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥ n0
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

Mathematical Representation of Omega notation :

➢ Theta Notation (Θ-Notation):

 Let g and f be the function from the set of natural numbers to itself. The function f is said to be
Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n)
for all n ≥ n0
Mathematical Representation of Theta notation:
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n)
for all n ≥ n0}