UNIT-I

Introduction and Overview- Elementary Data Organization, Data

Structures classification, Data Structure Operations, Algorithms:
Complexity, Time-Space Tradeoff. Preliminaries-Mathematical Notation
and Functions, Algorithmic Notation, Control Structures used in
algorithms, Complexity of Algorithms. Other Asymptotic Notations, Sub
algorithms, Variables, Data Types
.

DEPARTMENT OF COMPUTER SCIENCE

SPACES DEGREE COLLEGE
PAYAKARAOPETA

1
Data and Data Item:
Data are simply collection of facts. Data represents values or set of values.
A data item refers to a single unit of value. Data items that can be divided into sub
items are called group items and those that can’t be divided are called elementary
items.

In the above example ( ID, Age, Gender, First, Middle, Last, Street, Area ) are
elementary data items, whereas (Name, Address ) are group data items.
Q) Explain about Data Representation in computers?
Data Representation:
It refers to the form in which the data is stored, processed and transmitted.

 Data can be represented using methods like Integer, Real numbers, Character
and Strings.
 The Basic unit of data representation is a Bit i.e. either 0 or 1. The combination
of bit values can be used to represent the data.
 Eight bits together form 1 byte which represents a character. One or more
characters form a string.

2
INTEGER REPRESENTATION:

 Integer is a basic type commonly used to store negative as well as positive nos.
 The positive no’s are represented by Binary Number System. In this each bit
position represents the power of 2. The right most bit represent 2 0 which is 1 ,
21 which is 2 , next 22 which is 4 and so on.
For Example
The integer 38 is represented as 00100110

 The Negative no’s are represented by methods like 1’s complement and
2’s Complement.

 The 2’s Complement means 1’s complement + 1.

In 1’s complement the number is represented by complementing each bit i.e
changing 0 to 1 & 1 to 0.

REAL NUMBER REPRESENTATION:

 Real no’s are numbers with at least one decimal point.

 The methods used to represent real no’s in computers is floating-point
notation.
 In this notation, a real no is represented by a number called mantissa, times a
base raised to integer power called exponent.
 For example, if the base is fixed as 10 then
209.52 is represented as 20952 x 10-2
Mantissa is 20952 and Exponent is -2
20952 00000000000 0101000111011(24bits)
-2  11111110 (8bits)
Thus , the number is represented as 00000000000 0101000111011.11111110

3
CHARACTER REPRESENTATION:
 Character can be a alphabet, digit or special symbol. To represent data like
name of employee we use group of characters.
 There are different codes to store data in character form such as BCD,
EBCDIC, ASCII, UNICODE e.tc.
 BCD code uses 4bits to store data, EBCDIC code uses 8bits to store data,
ASCII Code uses 7 bits to store data, EASCII code uses 8bits to store the data
and UNICODE uses 16 bits to store the data.

For example, if 8 bits are used to represent a character, then 2 8=256 characters can
be represented as bit patterns.

‘A’ - 65 (ASCII Code) - 01000001

‘B’ - 66 (ASCII Code) - 01000010

Q) What is Datatype? Explain different primitive Datatypes?

(**vimp**)
 Datatype specifies the type of data and memory allocated to an identifier.
 It is an abstract concept defined by set of logical properties.
 A method of interpreting a bit pattern is often referred to as datatype.
Need of Datatype:
 To facilitate minimum use of memory
 Way to interpret the bit strings for different type of data. For example , in
negative integers the bit 1 is stored in MSB(Most Significant Bit) and in float
type the mantissa and exponent are stored in some pattern.
Primitive Datatypes:
 Each programming language has its own set of datatypes called built-in
datatypes or primitive datatypes.
 These are Basic Datatypes of any language that form the basic unit of
data structure defined by the user.
 It defines how the data will be internally represented, stored and Retrieved
from the memory.

4
For Example:

LANGUAGES BUILT IN DATA TYPES

FORTRAN INTEGER, REAL, LOGICAL, CHARACTER etc.

Pascal Integer, Real, Character, Boolean

int, float, double, char, unsigned int, signed int etc.

C

C++ int, float, double, char etc.

Java byte, short, int, long, char float, double, boolean, etc.

 Mostly they are mapped to Native datatypes of computer.

 A Few primitive datatypes are
1) Integer datatype
2) Character datatype
3) Float/Real datatype
Integer Datatype:
 Integer is a primitive datatype that stores integers without decimal point.
 They represent a range of numbers from -2n-1 to 2n-1 -1.
Where n depends on no of bits
For eg:
If n=16 has range from -215 to 215-1

Character Datatype:
 In this type, the information is represented in the form of characters. A
character can be Alphabet, Digit or Special Symbol.
 Any symbol from A-Z, a-z , 0-9, Special symbols like #,@,$ etc is a character
 The range of character type is 0 to 2n-1
Where n indicates no of bits
Eg:
In C, each character occupies 1 Byte (8bits)
5
So it has 28 =256 characters.

Float/ Real Datatype:

 A float datatype stores real numbers with at least one decimal point.
 A real number consists of two parts called mantissa & Exponent.
 A real number is generally denoted by floating point notation.
 A floating-point notation is expressed as
mxnr
where m is mantissa, n is base (fixed as 10) and r is exponent
 Floating point representation is used to store numbers which are extremely
large or extremely small.
 The range of float datatype is from 3.4 x 10 -38 to 3.4 x 1038
 Ex: 3.14
Q) Explain about Abstract Data Type (ADT)? (****vvvimp****)
 ADT stands for Abstract Datatype and is a mathematical model of data
objects that make up a data and functions that operate on the data.
 ADT do not have implementation details.
For eg:
INTEGER ARRAY

Abstract view:
 Store set of integer type elements
 Read elements by index
 Modify the elements by Index
 Perform sorting & searching.

 ADT is the specification of logical and mathematical properties of data type.

 ADT specifies only what operations to be performed but not how the
operations will be implemented.
 The implementation of ADT involves the translation of ADT Specification
into syntax of particular programming language.

6
 The Examples of ADT are Arrays, structures, Stacks, Queues, Trees, Graphs
e.tc

For Example ADT Specification for Stack:

Stack is a finite set of elements, where insertions and deletions take place
from one end called TOP.
Specification for ADT Stack is as follows:
Abstract: PUSH (data)
Precondition: top!=n
Operation : insert(data)
Topdata ( top points to most recent data)
Abstract: POP()
Precondition: top!=NULL
Operation : Remove(Top)
Topcurrent data

 Sometimes, these Abstract data types are also known as user defined data
types.
 For Example, if the user wants to process a Date type of data in the form of
dd /mm /yy. Such type of data type is not available in any built-in types and
hence we derive an abstract data type named as date.
struct Date
{
int dd;
int mm;
int yy;
}

ADT Properties:

 Domain(D): It specifies the range of values.

 Functions(F): It specifies the set of operations.
7
 Axioms: (A): It specifies the set of rules to implement functions.

It can be easily revealed that triplet {D, F, A} is nothing but an abstract data type.
For example, we know integer data type “int” in c language has following
properties

 D= {…-3,-2,-1,0, ±1, ±2, ±3 . . .}

 F= {+, -, *, /, %}
 A= {Format for storing Integer Numbers}

Q) Write short notes on Data Structures (5m)

 Organizing the data on computer’s memory is called as data structure. It is

mathematical or logical model of arrangement of data in computer memory.
 Data structure can be defined as structural relationship present within the
dataset.
 It also refers to set of computer variables that are connected in some
mathematical or logical manner.
 Data Structures mainly focus on interface and implementation:
 Interface: Interface represents the set of operations that a data structure
supports.
 Implementation: Implementation provides the internal representation of a
data structure.
Characteristics of a Data structure

 Correctness: Data structure should implement its interface correctly.

 Time Complexity: Running time of operations of data structure must be as
small.
 Space Complexity: Memory usage of a data structure operation should be as
little.

Need for Data Structure:

 To increase data searching

 To increase processor speed.
 To accept multiple requests
 It gives different level of organising data.

8
 It tells how data can be stored and accessed.
 Provide a means to manage huge amount of data efficiently.
Operations on Data Structures:

1. Inserting: the process of adding elements to the data structure is known as

“Insertion operation”.

2. Deleting: The process of removing an element or set of elements from the

data structure is known as “Deleting operation”.

3. Traversing: The process of visiting each and every data element is known as
“Traversing operation”.

4. Sorting: The process of arranging the given data elements either in ascending
or descending order is known as “sorting operation”.

5. Searching: The process of finding an element in a given data structure is

known as “searching operation”.

6. Modifying: The process of modifying an element in a given data structure is

known as “modifying operation”.

7. Merging: The process of combining two data structures into a single data
structure is known as “merging operation”.

Q) Explain different types of Data Structures (****vimp*****)

 Organizing the data on computer’s memory is called as data structure. It is

mathematical or logical model of arrangement of data in computer memory.
 Data structure can be defined as structural relationship present within the
dataset.
 It also refers to set of computer variables that are connected in some
mathematical or logical manner.
 The data structures are classified into two categories.
1. Primitive data structures
2. non-Primitive data structures

9
Primitive data structures:

 These are Basic data structures that directly operate using the machine
instructions.
 These Data Structures takes only one value at a time.

The list of primitive data structures are

1. Integer: It is used to represent a number without decimal point

2. Float: It is used to represent a number with at least one decimal point
3. Character: It is used to represent a single character
4. Boolean: It is used to store either true or false

Non-Primitive data structures:

 These are more complicated Data Structures derived from the primitive data
structures.
 They emphasize on grouping same or different data items with relationship
between them.
 These data structures are divided into two categories. They are
 Linear Data Structures
 Non-Linear Data Structures.

Linear Data structures:

 Linear data structure is a Data Structure in which the data items or elements are
organised Linearly or Sequentially.
 It is a list which shows the relationship of adjacency between the elements.
10
 All the data items(elements) in a linear data structure can be traversed in single
run.
 It includes arrays, linked list, stack and queue data structures.

1. Arrays: Array is a group of consecutive memory locations that stores

homogenous or same type of data. Each element of an array is referenced index
or subscript no.

2. Linked list: Linked list is a collection of Nodes. Node consists of two parts:
data and Link. Data presents elements and Link represents the address of next
node.

3. Stack: Stack is a linear list of elements in which the element is inserted or

deleted at one end called Top. It is follows Last-in-First-out (LIFO)
organisation.

11
4. Queue: Queue is a linear list of elements in which the elements are added at one
end called rear and deleted from another end called front. It follows first-in-
First-out (FIFO) organisation.

Non-Linear Data Structures:

 It is a data structure where the data items or elements are not organized
sequentially is called non-linear data structure.
 In this, the data elements of the non-linear data structure could be connected to
more than one element
 All the data elements in non-linear data structure cannot be traversed in single
run.
 Examples of non-linear data structures are:
 Trees
 Graphs
Tree:

A tree is collection of nodes where these nodes are arranged hierarchically and form
a parent child relationship.

Graph:

A Graph is a collection of a finite number of vertices and edges. Edges represent

relationships among vertices.

12
Q) Differentiate between Linear & Non-Linear Data structure? (5m)***
S.NO Linear Data Structure Non-linear Data Structure

In a linear data structure, data In a non-linear data structure, data

elements are arranged in a elements are arranged in non-linear
1. linear manner. manner.

In linear data structure, single Whereas in non-linear data structure,

2. level is involved. multiple levels are involved.

3. Its implementation is easy It’s implementation is complex.

In linear data structure, data While in non-linear data structure,

elements can be traversed in a data elements can’t be traversed in a
4. single run only. single run.

While in a non-linear data structure,

In a linear data structure, memory is utilized in an efficient
memory is not utilized in an way.
5. efficient way.

Its examples are: array, stack, While its examples are: trees and
6. queue, linked list, etc. graphs.

Applications of linear data

structures are mainly in Applications of non-linear data
application software structures are in Artificial Intelligence
7. development. and image processing.

13
DATA STRUCTURES:

 Data structure is a way of storing & organising the data in computer memory.
 It refers to collection of variables that are connected in some specific manner.
 Data structure can be defined as structural relationship present within the
dataset.

Q) what is Algorithm and Different Approaches in Designing an

Algorithm?
Algorithm means step by step representation of instructions to solve a problem.

An algorithm can be expressed in three ways: -

(i) in any natural language such as English, called pseudo code.
(ii) in a programming language or
(iii) in the form of a flowchart.
Characteristics of algorithm:

1) INPUT: It takes one or more data as inputs.

2) OUTPUT: The result should be available to user after the algorithm terminates.
3) DEFINITENESS: Each instruction must be clear
4) FINITENESS: An algorithm must terminate after a finite number of steps.
5) EFFECTIVENESS: Instructions must be simple and carried out in a finite time.
6) Should be Unambiguous
7) Repetitions of instructions should be avoided.
8) Each instruction should be unique and concise.
The Efficiency of algorithm is determined by the Space Complexity and Time
Complexity.
Space Complexity is the amount of Memory space required to run an algorithm to
complete.

14
Time Complexity is the amount of Computational or Execution time required to run
an algorithm to complete.
Approaches in Designing Algorithms: (******vimp*******)
 A complex program or system is divided into small units called Modules.
 The modularity enhances Design clarity, Debugging, Testing, Documentation
and Maintenance.
 Algorithm design involves two approaches. They are
 TOP-DOWN APPROACH
 BOTTOM-UP APPROACH.

TOP-DOWN APPROACH:
 It is an approach of decomposing a complex module/component into sub
modules/components.
 In this the Higher-level component is decomposed into lower-level
components.
 Top-Down design method takes the form of step-wise Refinement.
 In this we start with the top module and incrementally add sub modules in next
levels of refinement.
 In each step, design is refined into most concrete level.
 This approach is mainly used by structured oriented programming languages
like C, COBOL, PASCAL etc.

BOTTOM-UP APPROACH:
 It is an approach of designing the basic or primitive modules and proceeds to
higher level components.
 In this the lower-level components are composed to form the higher-level
component.
 Bottom-up design method works with levels of abstraction.
 Starting from bottom layer the operations that provide layer abstraction is
implemented and these are used to design still higher level of abstraction.
15
 This approach is mainly used by object oriented programming languages like
c++, java , python etc.

Q) Differentiate between Top-Down Approach and Bottom-Up Approach?

(vvimp)

In bottom up approach, the smaller

In this approach the higher level components are designed and
components are decomposed into composed to form Higher level
1. lower level components Components

Mainly used by structured Mainly used by object oriented

programming language such as programming language such as C++,
2. COBOL, Fortran, C, etc. C#, Python.

Redundancy may occur as each Redundancy is minimized by using

3. part is programmed separately. data encapsulation and data hiding.

4. It uses Decomposition principle It uses Composition principle

It takes the form of Step wise It takes the form of levels of

5. Refinement Abstraction

It is used in debugging, module

6. documentation, etc. It is used for Testing

In this the communication is less It maintains communication between

7. between the modules modules.

8. It is mainly function oriented It is mainly data oriented

It uses the Data Encapsulation and

9 It doesn’t include Data Hiding Data hiding

16
Breakdown of problem takes
10 place Integration of Modules takes place.

Q) Explain about the Time Complexity and Space Complexity? (OR) Explain
about the Analysis of Algorithms (***vimp)

 An algorithm must be analyzed to determine its resources like Execution time,

Memory etc.
 The Efficiency of algorithm is determined by the Space Complexity and Time
Complexity.
 The space and time complexity is known as Computational complexity.
 The time and space complexity depends upon the size of the problem.
Time Complexity:
Time Complexity is the amount of Execution time required to run an algorithm to
complete.
Generally it is measured by developing the frequency count for all key statements.
Consider the following algorithms

17
The total frequency count of the algorithms - A, B and C given by 1, (2n+1) and
(2n2+2n+1) respectively are expressed as O(1), O(n) and O(n2).

 There are different time complexities analysed by the algorithm. They are
 Best Case Time Complexity
 worst Case Time Complexity
 Average Case Time Complexity.
 Best Case Time Complexity:
It is the measure of minimum time required by an algorithm to execute for an
input of size n.
 worst Case Time Complexity:
It is the measure of Maximum time required by an algorithm to execute for an
input of size n.
 Average Case Time Complexity:
It is the time required by an algorithm to execute for an input of size n.

18
If an algorithm performs f(n) basic operations when size of input is n, then the total
running time will be c.f(n).Where c is constant
Space Complexity
Space Complexity is the amount of Memory space required to run an algorithm to
complete.
It includes
a) Fixed Space: This includes the space for simple variables, fixed size
structured variable and constants
b) Variable Space: This includes the space needed by structured variables whose
size depends on particular instance of variables. It also includes the additional
space required when the function uses recursion.

S(P)=C + SP
Where S(P) is the Space Complexity
C is the fixed Space
SP is the Variable space

19
Q) Write Short notes on Big ‘O’ Notation? (*****VVIMP*****)
 Big O notation is an asymptotic notation that measures the performance or

analysis of an algorithm.

 It measures the worst case of time complexity.

 It helps to determine the time complexity as well as the space complexity of

algorithms.

 Most common computing times of algorithm are

O(1) - constant.

O(n) - linear

O(n2) - quadratic.

O(n3) - cubic.

O(2n) – Exponential

O(logn), O (nlog n) – logarithmic time

O(1) < O(log n)< O(n)<O(n log n)< O(n2) < O(n3)< O(2n)

 The BIG O is defined as follows

If f(n) is the computing time of an algorithm and g(n) represents a standard

function like 1,n,n2,n3,nlogn etc then f(n) = O(g(n)) if there exists constant C

and positive integer n0 such that: f(n)≤c.g(n) for all n≥no .

20
 This notation provides an upper bound on a function which ensures that the

function never grows faster than the upper bound.

 It is the formal way to express the upper boundary of an algorithm’s running

time.

 This implies that g(n) is an upper bound on the function f(n).

 It is used by programmers to design and select efficient algorithms in terms of

space and time complexity.

 Graphical representation of Big O

Example : f(n)=2n+3 , g(n)=n

Now, we have to find is f(n)=O(g(n))

To check f(n)=O(g(n)), it must satisfy the given condition:

f(n)<=c.g(n)
Let f(n) = 2n+3 and g(n) = n.
Then f(n)<=c.g(n)
2n+3 <= c.n
Let's assume c=5
2n+3<=5*n

21
F(n)=Og(n)=O(n) for n>=1

Q) Explain about Time Space Trade-off algorithms?

 The time-space trade-off in algorithms and data structures refers to balancing
memory usage (space) against computational speed (time).
 When designing algorithms, sometimes you can reduce the time complexity of
a solution by using more memory or save memory by allowing the algorithm
to take longer.
 This trade-off is crucial in optimizing performance based on the available
resources and requirements of an application.
1. Space-Optimized Algorithms
Example: Storing sorted arrays rather than an entire binary search tree (BST) saves
space but can increase the time required for insertion, as an array requires shifting
elements.
2. Time-Optimized Algorithms
Example: Caching or Memoization. Storing precomputed results in a cache speeds up
repeated computations, at the expense of using additional memory.
Types of Time-Space Trade-Offs
Explicit Trade-Offs: When you choose between two specific implementations (e.g.,
array vs. linked list, dynamic programming vs. recursive computation).
Implicit Trade-Offs: When inherent design choices in an algorithm impose certain
time-space requirements (e.g., storing intermediate results for optimization).
Examples of Algorithms with Time-Space Trade-Offs
Sorting Algorithms: Quick Sort uses extra memory for recursion stack but is usually
faster than algorithms like Bubble Sort, which use constant memory.
Binary Search Trees (BSTs) vs. Arrays: BSTs use more memory but allow faster
searches and insertions than sorted arrays, especially for dynamic data.
22
Balancing Time-Space Trade-Off
To optimize time and space:
 Consider the constraints of the problem, like memory limits or performance
requirements.
 Select the right data structure (e.g., hash tables for fast access, compressed
data if memory is limited).
 Use profiling to determine which approach best fits the context (such as a
server environment where memory is abundant, or mobile where memory is
limited).
Q) Explain about Preliminaries-Mathematical Notation

Mathematical functions play a fundamental role in data structures (DS), especially in

analyzing and designing efficient algorithms.

1. Polynomial Functions

Definition: Polynomial functions are expressed as

2. Logarithmic Functions

23
3. Exponential Functions

4. Factorial Functions

The factorial function is denoted n!n! and represents the product of all positive
integers up to n (i.e., n!=n×(n−1)×…× 1).

Application in Data Structures: Factorial functions indicate that an algorithm’s

time complexity grows extremely fast, often due to permutations or combinations.

5. Modular Arithmetic

6. Floor and Ceiling Functions

24
7. Summation (∑) and Product (π) Notations

Summation notation ∑: Represents the sum of a sequence of numbers.

Product notation π : Represents the product of a sequence of numbers.

8. Recurrence Relations

Recurrence relations are equations that express the overall time complexity of
recursive algorithms in terms of smaller subproblems.

Q) Explain about Control Statements ?

 By default the statements in C are executed sequentially. In order to change the

order of sequence of execution we use control statements.
 The control statement specifies the flow of data.

In C control statements are classified into two types. They are

• Decision control statements

• Looping Statements

Decision Control Statements:

Decision control statements execute the statements by the checking condition. The
decision making involves branching, which means jumping from one step to step in a
program.

Conditional Branching Statements:

If branching occurs basing on condition then it is known as conditional branching. C

supports the following decision control and branching statements

❖ Simple if statement

❖ if..else statement

❖ if..else if statement

❖ Nested if

❖ Switch statement

25
✓ Simple if:

The simple if statement is used to execute a statement/block if the condition is true

otherwise the statement/block will be skipped.

syntax:

if(condition)

statement/block

Eg:

if (age>=18)

printf(“eligible for vote”);

✓ if..else:

In this statement we have two blocks or statements, if the condition is true then the
statement1/block1 is executed otherwise the statement2/block2 will be executed.

Syntax:

if (condition)

Statement1/block;

Else

Statement2/block;

Eg:

if (n >0)

printf(“%d is positive”,n);

else

printf(“%d is negative”,n);

✓ if..else if:

It is used to check multiple conditions. It is also known as ladder if.

It is a chain of if statements in which each statement within else is an if statement.

Syntax: if (condition1)

26
statement1/block1;

else if (condition 2)

statement2/block2;

..............

else if (condition N)

statement/blockn;

eg:

if (avg>=60)

printf(“first class”);

else if(avg>=50)

printf(“second class”);

else if(avg>=35)

printf(“third class”);

✓ Nested if:

An if statement within another if statement is known as Nested If.

Syntax:

if (condition1)

if (condition2)

Statement1/block1 ;

else

Statement2/block2;

if (condition3)

Statement3/block3;

else statement4/block

27
eg :

if (a>b)

if( a>c)

printf(“a is big”);

else

if(b>c)

printf(“b is big”);

else

printf(“c is big”);

✓ switch:

It is a multi-way decision statement. It is used to select a statement(s) out of several

available groups.

Syntax:

switch(expression)

case const1: statement1/block1;

break;

case const2: statement2/block2;

break;

...................................................

.................................................

case constn: statement n/blockn;

break;

[default: default statement;

28
Eg: switch(month)

case 1:

case 3:

case 5:

case 7:

case 8:

case 10:

case 12:printf(“31 days ”);break;

case 4:

case 6:

case 9:

case 11: printf(“30 days”);break;

case 2: printf(“28 days”);break;

default:printf(“invalid month”);

Looping (or) Iteration Statements:

Looping is the process of repetition of instructions. Every loop contains initial value,
condition

and increment/decrement.

C supports 3 types of iterative or looping statements. They are

❖ while loop

❖ do-while loop

❖ for loop

29
while loop:

❖ It is an entry –controlled loop statement, which repeats the instructions until

condition is satisfied.

❖ It enters into loop by checking the condition at first.

❖ It enter’s into loop minimum zero times if the condition is not satisfied.

Syntax:

initial value;

while (condition)

eg: i=1;

while(i<=10)

Statements; printf(“%d”,i);

Increment/decrement;

i++;

do-While loop:

❖ It is an exit –controlled loop statement, which repeats the instructions until

condition is satisfied.

❖ In this the condition is checked at last .

❖ It enter’s into loop minimum 1 time even if the condition is not satisfied.

Syntax:

initial value;

do

statements;
30
Increment/decrement;

}while(condition);

eg:

i=1;

do

printf(“%d”,i);

i++;

}while(i<=10);

For loop is an entry controlled loop statement that is used to repeat the loop for fixed
no of times.

It checks the condition at first and then enters into the loop.

Syntax:

for(intial value; condition;increment/decrement)

body;

The initial value specifies the starting value, condition specifies the no of times the
loop to be repeated and increment/decrement specifies the next iteration value.

Eg: for(i=0;i<=100;i++)

printf(“%d”,i);

Q) Explain about sub algorithms

 In data structures and algorithms, sub-algorithms refer to smaller, often
reusable algorithms or procedures that help achieve specific tasks within a
larger algorithm.

31
 These sub-algorithms can simplify complex processes, improve readability,
and make code more modular.
 They are commonly used for fundamental operations within data structures,
breaking down complex tasks, and optimizing efficiency.

1. Search Algorithms

Linear Search: Checks each element in a list sequentially until the desired element is
found or the list ends. Often used for unsorted data.

Complexity: O(n)

Binary Search: Finds an element in a sorted list by repeatedly dividing the search
interval in half, which reduces the search time significantly.

Complexity: O(logn)

2. Sorting Algorithms

Sorting algorithms are used to arrange elements in a certain order, typically

ascending or descending, and are essential for efficient searching and organizing
data.

Bubble Sort: A simple sorting algorithm that repeatedly swaps adjacent elements if
they are in the wrong order.

Complexity:

O(n2)

Merge Sort: A divide-and-conquer sorting algorithm that splits the list into smaller
sublists, sorts them, and then merges them.

Complexity: O(nlogn)

Quick Sort: A divide-and-conquer algorithm that selects a "pivot" and partitions the
array around the pivot so that elements on the left are less than the pivot, and
elements on the right are greater.

Complexity: Average O(nlogn),

worst-case O(n2)

3. Insertion Algorithms

Insertion sub-algorithms are often used for adding elements to data structures such as
arrays, linked lists, trees, and hash tables.

32
Array Insertion: Adds an element at a specific index in an array by shifting
elements.

Complexity: O(n)

Linked List Insertion: Inserts an element at the beginning, middle, or end of a

linked list.

Complexity: O(1) for head or tail insert,

O(n) for general case

Binary Search Tree Insertion: Inserts an element in a binary search tree while
maintaining its properties.

Complexity: Average O(logn),

worst-case O(n)

4. Deletion Algorithms

Deletion algorithms remove elements from data structures, such as arrays, linked
lists, and trees, often while maintaining structural properties.

Array Deletion: Removes an element at a specific index by shifting elements.

Complexity: O(n)

Linked List Deletion: Deletes an element by updating pointers.

Complexity: O(1) if the pointer to the node is given,

O(n) for search and delete

Binary Search Tree Deletion: Deletes a node from a binary search tree while
maintaining its properties.

Complexity: Average O(logn), worst-case O(n)

5. Traversal Algorithms

Traversal algorithms visit each element in a data structure, typically to process or

retrieve values.

Array Traversal: Accesses each element sequentially in an array.

Complexity: O(n)

Linked List Traversal: Accesses each node sequentially by following pointers.

33
Complexity: O(n)

Tree Traversal: Visits nodes in a tree in a specific order.

Preorder: Root, Left, Right

Inorder: Left, Root, Right (used in binary search trees for sorted order)

Postorder: Left, Right, Root O(n) for all traversal types

Q)Explain about different asymptotic notations ?

 Asymptotic notation is a mathematical tool used in computer science to
describe the behavior of algorithms as their input size grows.
 It provides a way to evaluate the efficiency and performance of algorithms.
 specifically in terms of time complexity (how the running time grows) and
space complexity (how the memory usage grows).

The three main types of asymptotic notations are:

Big O Notation O(f(n)):

If f(n) is the computing time of an algorithm and g(n) represents a standard function
like 1,n,n2,n3,nlogn etc then f(n) = O(g(n)) if there exists constant C and positive
integer n0 such that: f(n)≤c.g(n) for all n≥no .

Use: measures the performance or analysis of an algorithm.It measures the worst

case of time complexity.It helps to determine the time complexity as well as the
space complexity of algorithms.

Big Omega Notation Ω(f(n)):

Big Omega notation describes a lower bound on the time complexity of an algorithm,
showing the best-case scenario. It represents the minimum time the algorithm will
take.

Use: It helps in understanding the minimum time the algorithm requires, which can
be useful for determining the efficiency in the most favorable conditions.

Big Theta Notation θ(f(n)):

Big Theta notation provides a tight bound on the time complexity, describing both
the upper and lower bounds. It indicates that the algorithm’s running time grows
asymptotically as f(n)

34
Use: This notation is helpful for analyzing algorithms with predictable growth rates.

35