UNIT - I Introduction to data structure and algorithm (08 Hours)

Introduction to data structures, Classification of Data Structures, Primitive Data

Types, Abstract Data Types abstract data types (ADT), Introduction to
algorithms, Importance of Algorithm Analysis, characteristics of algorithms,
algorithm design tools: pseudo code and flowchart, relationship among data,
Complexity of an Algorithm, Asymptotic Analysis and Notations.

Introduction to data structures, Classification of Data Structures

What is Data Structure:

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that
can be accessed and updated efficiently.

A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing data.
Different basic and advanced types of data structures are used in almost every program or software system that has be
developed. So we must have good knowledge of data structures.

Data Type Data Structure

The data type is the form of a variable to Data structure is a collection of different kinds
which a value can be assigned. It defines that of data. That entire data can be represented
the particular variable will assign the values using an object and can be used throughout the
of the given data type only. program.
It can hold value but not data. Therefore, it is It can hold multiple types of data within a
dataless. single object.
The implementation of a data type is known Data structure implementation is known as
as abstract implementation. concrete implementation.
There is no time complexity in the case of In data structure objects, time complexity plays
data types. an important role.
While in the case of data structures, the data
In the case of data types, the value of data is and its value acquire the space in the
not stored because it only represents the type computer’s main memory. Also, a data
of data that can be stored. structure can hold different kinds and types of
data within one single object.
Data structure examples are stack, queue, tree,
Data type examples are int, float, double, etc.
etc.

Classification of Data Structure:

Data structure has many different uses in our daily life. There are many different data structures that are used to solve
different mathematical and logical problems. By using data structure, one can organize and process a very large amou
of data in a relatively short period. Let’s look at different data structures that are used in different situations.
  Linear data structure: Data structure in which data elements are arranged sequentially or linearly, where each
element is attached to its previous and next adjacent elements, is called a linear data structure.
Examples of linear data structures are array, stack, queue, linked list, etc.
1. Static data structure: Static data structure has a fixed memory size. It is easier to access the elements in a static
data structure.
An example of this data structure is an array.
2. Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be randomly updated during
runtime which may be considered efficient concerning the memory (space) complexity of the code.
Examples of this data structure are queue, stack, etc.

 Non-linear data structure: Data structures where data elements are not placed sequentially or linearly are calle
non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single run only
Examples of non-linear data structures are trees and graphs.
 Need Of Data structure :
The structure of the data and the synthesis of the algorithm are relative to each other. Data presentation must be easy t
understand so the developer, as well as the user, can make an efficient implementation of the operation.
Data structures provide an easy way of organizing, retrieving, managing, and storing data.
Here is a list of the needs for data.
1. Data structure modification is easy.
2. It requires less time.
3. Save storage memory space.
4. Data representation is easy.
5. Easy access to the large database.

A. Arrays:
An array is a linear data structure and it is a collection of items stored at contiguous memory locations. The idea is to
store multiple items of the same type together in one place. It allows the processing of a large amount of data in a
relatively short period. The first element of the array is indexed by a subscript of 0. There are different operations
possible in an array, like Searching, Sorting, Inserting, Traversing, Reversing, and Deleting.
Characteristics of an Array:
An array has various characteristics which are as follows:

 Arrays use an index-based data structure which helps to identify each of the elements in an array easily using
index.
 If a user wants to store multiple values of the same data type, then the array can be utilized efficiently.
 An array can also handle complex data structures by storing data in a two-dimensional array.
 An array is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
 The search process in an array can be done very easily.
Operations performed on array:
 Initialization: An array can be initialized with values at the time of declaration or later using an assignment
statement.
 Accessing elements: Elements in an array can be accessed by their index, which starts from 0 and goes up to t
size of the array minus one.
 Searching for elements: Arrays can be searched for a specific element using linear search or binary search
algorithms.
 Sorting elements: Elements in an array can be sorted in ascending or descending order using algorithms like
bubble sort, insertion sort, or quick sort.
 Inserting elements: Elements can be inserted into an array at a specific location, but this operation can be time
consuming because it requires shifting existing elements in the array.
 Deleting elements: Elements can be deleted from an array by shifting the elements that come after it to fill the
gap.
 Updating elements: Elements in an array can be updated or modified by assigning a new value to a specific in
 Traversing elements: The elements in an array can be traversed in order, visiting each element once.
These are some of the most common operations performed on arrays. The specific operations and algorithms used ma
vary based on the requirements of the problem and the programming language used.

Applications of Array:
Different applications of an array are as follows:

 An array is used in solving matrix problems.

 Database records are also implemented by an array.
 It helps in implementing a sorting algorithm.
 It is also used to implement other data structures like Stacks, Queues, Heaps, Hash tables, etc.
 An array can be used for CPU scheduling.
 Can be applied as a lookup table in computers.
 Arrays can be used in speech processing where every speech signal is an array.
 The screen of the computer is also displayed by an array. Here we use a multidimensional array.
 The array is used in many management systems like a library, students, parliament, etc.
 The array is used in the online ticket booking system. Contacts on a cell phone are displayed by this array.
 In games like online chess, where the player can store his past moves as well as current moves. It indicates a h
of position.
 To save images in a specific dimension in the android Like 360*1200
Real-Life Applications of Array:
 An array is frequently used to store data for mathematical computations.
 It is used in image processing.
 It is also used in record management.
 Book pages are also real-life examples of an array.
 It is used in ordering boxes as well.

B. Linked list:
A linked list is a linear data structure in which elements are not stored at contiguous memory locations. The elements
linked list are linked using pointers as shown in the below image:

Types of linked lists:

 Singly-linked list
 Doubly linked list
 Circular linked list
 Doubly circular linked list

Characteristics of a Linked list:

A linked list has various characteristics which are as follows:

 A linked list uses extra memory to store links.

 During the initialization of the linked list, there is no need to know the size of the elements.
 Linked lists are used to implement stacks, queues, graphs, etc.
 The first node of the linked list is called the Head.
 The next pointer of the last node always points to NULL.
 In a linked list, insertion and deletion are possible easily.
 Each node of the linked list consists of a pointer/link which is the address of the next node.
 Linked lists can shrink or grow at any point in time easily.
Operations performed on Linked list:
A linked list is a linear data structure where each node contains a value and a reference to the next node. Here are som
common operations performed on linked lists:

 Initialization: A linked list can be initialized by creating a head node with a reference to the first node. Each
subsequent node contains a value and a reference to the next node.
 Inserting elements: Elements can be inserted at the head, tail, or at a specific position in the linked list.
 Deleting elements: Elements can be deleted from the linked list by updating the reference of the previous node
point to the next node, effectively removing the current node from the list.
 Searching for elements: Linked lists can be searched for a specific element by starting from the head node and
following the references to the next nodes until the desired element is found.
 Updating elements: Elements in a linked list can be updated by modifying the value of a specific node.
 Traversing elements: The elements in a linked list can be traversed by starting from the head node and followi
the references to the next nodes until the end of the list is reached.
  Reversing a linked list: The linked list can be reversed by updating the references of each node so that they po
to the previous node instead of the next node.
 These are some of the most common operations performed on linked lists. The specific operations and algorith
used may vary based on the requirements of the problem and the programming language used.

Applications of the Linked list:

Different applications of linked lists are as follows:
 Linked lists are used to implement stacks, queues, graphs, etc.
 Linked lists are used to perform arithmetic operations on long integers.
 It is used for the representation of sparse matrices.
 It is used in the linked allocation of files.
 It helps in memory management.
 It is used in the representation of Polynomial Manipulation where each polynomial term represents a node in t
linked list.
 Linked lists are used to display image containers. Users can visit past, current, and next images.
 They are used to store the history of the visited page.
 They are used to perform undo operations.
 Linked are used in software development where they indicate the correct syntax of a tag.
 Linked lists are used to display social media feeds.
Real-Life Applications of a Linked list:
 A linked list is used in Round-Robin scheduling to keep track of the turn in multiplayer games.
 It is used in image viewer. The previous and next images are linked, and hence can be accessed by the previou
and next buttons.
 In a music playlist, songs are linked to the previous and next songs.

C. Stack:
Stack is a linear data structure that follows a particular order in which the operations are performed. The order is
LIFO(Last in first out). Entering and retrieving data is possible from only one end. The entering and retrieving of data
also called push and pop operation in a stack. There are different operations possible in a stack like reversing a stack
using recursion, Sorting, Deleting the middle element of a stack, etc

Characteristics of a Stack:
Stack has various different characteristics which are as follows:
 Stack is used in many different algorithms like Tower of Hanoi, tree traversal, recursion, etc.
 Stack is implemented through an array or linked list.
 It follows the Last In First Out operation i.e., an element that is inserted first will pop in last and vice versa.
 The insertion and deletion are performed at one end i.e. from the top of the stack.
In stack, if the allocated space for the stack is full, and still anyone attempts to add more elements, it will lead to stack
overflow.
Applications of Stack:
Different applications of Stack are as follows:
 The stack data structure is used in the evaluation and conversion of arithmetic expressions.
 It is used for parenthesis checking.
 While reversing a string, the stack is used as well.
 Stack is used in memory management.
 It is also used for processing function calls.
 The stack is used to convert expressions from infix to postfix.
 The stack is used to perform undo as well as redo operations in word processors.
 The stack is used in virtual machines like JVM.
 The stack is used in the media players. Useful to play the next and previous song.
 The stack is used in recursion operations.
Operation performed on stack ;
A stack is a linear data structure that implements the Last-In-First-Out (LIFO) principle. Here are some common
operations performed on stacks:
 Push: Elements can be pushed onto the top of the stack, adding a new element to the top of the stack.
 Pop: The top element can be removed from the stack by performing a pop operation, effectively removing the
element that was pushed onto the stack.
 Peek: The top element can be inspected without removing it from the stack using a peek operation.
 IsEmpty: A check can be made to determine if the stack is empty.
 Size: The number of elements in the stack can be determined using a size operation.
These are some of the most common operations performed on stacks. The specific operations and algorithms used ma
vary based on the requirements of the problem and the programming language used. Stacks are commonly used in
applications such as evaluating expressions, implementing function call stacks in computer programs, and many other

Real-Life Applications of Stack:

 Real life example of a stack is the layer of eating plates arranged one above the other. When you remove a pla
from the pile, you can take the plate to the top of the pile. But this is exactly the plate that was added most
recently to the pile. If you want the plate at the bottom of the pile, you must remove all the plates on top of it t
reach it.
 Browsers use stack data structures to keep track of previously visited sites.
 Call log in mobile also uses stack data structure.

D. Queue:
Queue is a linear data structure that follows a particular order in which the operations are performed. The order is Firs
First Out(FIFO) i.e. the data item stored first will be accessed first. In this, entering and retrieving data is not done fro
only one end. An example of a queue is any queue of consumers for a resource where the consumer that came first is
served first. Different operations are performed on a Queue like Reversing a Queue (with or without using recursion),
Reversing the first K elements of a Queue, etc. A few basic operations performed In Queue are enqueue, dequeue, fro
rear, etc
Characteristics of a Queue:
The queue has various different characteristics which are as follows:

 The queue is a FIFO (First In First Out) structure.

 To remove the last element of the Queue, all the elements inserted before the new element in the queue must b
removed.
 A queue is an ordered list of elements of similar data types.
Applications of Queue:
Different applications of Queue are as follows:

 Queue is used for handling website traffic.

 It helps to maintain the playlist in media players.
 Queue is used in operating systems for handling interrupts.
 It helps in serving requests on a single shared resource, like a printer, CPU task scheduling, etc.
 It is used in the asynchronous transfer of data e.g. pipes, file IO, and sockets.
 Queues are used for job scheduling in the operating system.
 In social media to upload multiple photos or videos queue is used.
 To send an e-mail queue data structure is used.
 To handle website traffic at a time queues are used.
 In Windows operating system, to switch multiple applications.
Operation performed on queue:
A queue is a linear data structure that implements the First-In-First-Out (FIFO) principle. Here are some common
operations performed on queues:

 Enqueue: Elements can be added to the back of the queue, adding a new element to the end of the queue.
 Dequeue: The front element can be removed from the queue by performing a dequeue operation, effectively
removing the first element that was added to the queue.
 Peek: The front element can be inspected without removing it from the queue using a peek operation.
 IsEmpty: A check can be made to determine if the queue is empty.
 Size: The number of elements in the queue can be determined using a size operation.
These are some of the most common operations performed on queues. The specific operations and algorithms used m
vary based on the requirements of the problem and the programming language used. Queues are commonly used in
applications such as scheduling tasks, managing communication between processes, and many others.

Real-Life Applications of Queue:

A real-world example of a queue is a single-lane one-way road, where the vehicle that enters first will exit first.
A more real-world example can be seen in the queue at the ticket windows.
A cashier line in a store is also an example of a queue.
People on an escalator
E. Tree:
A tree is a non-linear and hierarchical data structure where the elements are arranged in a tree-like structure. In a tree,
topmost node is called the root node. Each node contains some data, and data can be of any type. It consists of a centr
node, structural nodes, and sub-nodes which are connected via edges. Different tree data structures allow quicker and
easier access to the data as it is a non-linear data structure. A tree has various terminologies like Node, Root, Edge,
Height of a tree, Degree of a tree, etc.
There are different types of Tree-like
 Binary Tree,
 Binary Search Tree,
 AVL Tree,
 B-Tree, etc.

Characteristics of a Tree:
The tree has various different characteristics which are as follows:
 A tree is also known as a Recursive data structure.
 In a tree, the Height of the root can be defined as the longest path from the root node to the leaf node.
 In a tree, one can also calculate the depth from the top to any node. The root node has a depth of 0.
Applications of Tree:
Different applications of Tree are as follows:
 Heap is a tree data structure that is implemented using arrays and used to implement priority queues.
 B-Tree and B+ Tree are used to implement indexing in databases.
 Syntax Tree helps in scanning, parsing, generation of code, and evaluation of arithmetic expressions in Compi
design.
 K-D Tree is a space partitioning tree used to organize points in K-dimensional space.
 Spanning trees are used in routers in computer networks.
Operation performed on tree:
A tree is a non-linear data structure that consists of nodes connected by edges. Here are some common operations
performed on trees:
 Insertion: New nodes can be added to the tree to create a new branch or to increase the height of the tree.
 Deletion: Nodes can be removed from the tree by updating the references of the parent node to remove the
reference to the current node.
 Search: Elements can be searched for in a tree by starting from the root node and traversing the tree based on
value of the current node until the desired node is found.
  Traversal: The elements in a tree can be traversed in several different ways, including in-order, pre-order, and
post-order traversal.
 Height: The height of the tree can be determined by counting the number of edges from the root node to the
furthest leaf node.
 Depth: The depth of a node can be determined by counting the number of edges from the root node to the curr
node.
 Balancing: The tree can be balanced to ensure that the height of the tree is minimized and the distribution of
nodes is as even as possible.
These are some of the most common operations performed on trees. The specific operations and algorithms used may
vary based on the requirements of the problem and the programming language used. Trees are commonly used in
applications such as searching, sorting, and storing hierarchical data.

Real-Life Applications of Tree:

 In real life, tree data structure helps in Game Development.
 It also helps in indexing in databases.
 A Decision Tree is an efficient machine-learning tool, commonly used in decision analysis. It has a flowchart-
structure that helps to understand data.
 Domain Name Server also uses a tree data structure.
 The most common use case of a tree is any social networking site.

F. Graph:
A graph is a non-linear data structure that consists of vertices (or nodes) and edges. It consists of a finite set of vertice
and set of edges that connect a pair of nodes. The graph is used to solve the most challenging and complex programm
problems. It has different terminologies which are Path, Degree, Adjacent vertices, Connected components, etc.

Characteristics of Graph:
The graph has various different characteristics which are as follows:

 The maximum distance from a vertex to all the other vertices is considered the Eccentricity of that ver
 The vertex having minimum Eccentricity is considered the central point of the graph.
 The minimum value of Eccentricity from all vertices is considered the radius of a connected graph.
Applications of Graph:
Different applications of Graphs are as follows:

 The graph is used to represent the flow of computation.

 It is used in modeling graphs.
 The operating system uses Resource Allocation Graph.
 Also used in the World Wide Web where the web pages represent the nodes.

Operation performed on Graph:

A graph is a non-linear data structure consisting of nodes and edges. Here are some common operations performed on
graphs:
  Add Vertex: New vertices can be added to the graph to represent a new node.
 Add Edge: Edges can be added between vertices to represent a relationship between nodes.
 Remove Vertex: Vertices can be removed from the graph by updating the references of adjacent vertic
to remove the reference to the current vertex.
 Remove Edge: Edges can be removed by updating the references of the adjacent vertices to remove the
reference to the current edge.
 Depth-First Search (DFS): A graph can be traversed using a depth-first search by visiting the vertices i
depth-first manner.
 Breadth-First Search (BFS): A graph can be traversed using a breadth-first search by visiting the vertic
in a breadth-first manner.
 Shortest Path: The shortest path between two vertices can be determined using algorithms such as
Dijkstra’s algorithm or A* algorithm.
 Connected Components: The connected components of a graph can be determined by finding sets of
vertices that are connected to each other but not to any other vertices in the graph.
 Cycle Detection: Cycles in a graph can be detected by checking for back edges during a depth-first sea
These are some of the most common operations performed on graphs. The specific operations and algorithms
used may vary based on the requirements of the problem and the programming language used. Graphs are
commonly used in applications such as computer networks, social networks, and routing problems.

Real-Life Applications of Graph:

 One of the most common real-world examples of a graph is Google Maps where cities are located as
vertices and paths connecting those vertices are located as edges of the graph.
 A social network is also one real-world example of a graph where every person on the network is a no
and all of their friendships on the network are the edges of the graph.
 A graph is also used to study molecules in physics and chemistry.

Primitive Data Types

Primitive Data Types

Primitive data types are the basic building blocks for data manipulation in programming languages. They typically
include:

 Integers: Whole numbers (e.g., int, long).

 Floating-point numbers: Numbers with fractional parts (e.g., float, double).
 Characters: Single characters (e.g., char).
 Booleans: True or false values (e.g., bool).
 Primitive data structure Non Primitive Data structure
Non-Primitive data structure is a data structure
Primitive data structure is the data structure that allows
that allows you to store multiple data type
you to store only single data type values.
values.
integer, boolean, character, float, etc. are some Array, Linked List, Stack, etc. are some
examples of primitive data structures. examples of non-primitive data structures.
Primitive data structure always contains some value
You can store a NULL value in the non-
i.e. these data structures do not allow you to store
primitive data structures.
NULL values.
The size of the primitive data structures is dependent The size of the non-primitive data structure is
on the type of the primitive data structure. not fixed.

----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----
these data types are defined by default in the Programming languages type system, they come with a set of predef
operations. Such primitive types cannot have new operations defined. There are three more types of primitives in the
type system:

1. Short, int, long, float, and double are the numerical primitives. These primitive data types can only store numb
Simple arithmetic (addition, subtraction, etc.) or comparison operations are associated with such data types (gre
than, equal to, etc.)
2. Textual primitives include bytes and characters. Characters are stored in these primitive data types (that ca
Unicode alphabets or even numbers). Textual manipulation operations are associated with data types (compa
two words, joining characters to make words, etc.). However, byte and char can perform arithmetic operation
well.
3. Primitives with boolean and null values: boolean and null.

The actual number of primitive data types available is determined by the programming language that is used. Strings
instance, are a composite but built-in data type in C#, even as they are integrated to a primitive data type that is both b
and built-in in advanced accents of BASIC and JavaScript.

Considering the Java Programming language, the primitive data structures include integers, floats, characters, and poin
In general, there are 8 data types. They are as follows

o Boolean data type

o byte data type
o char data type
o short data type
o int data type
o long data type
 o float data type
o double data type

Boolean Data Type

A Boolean data type comprises a single bit of information that can only store true or false values. True or false condit
are tracked using this data type, and Boolean data types are also used to store the result of various conditions. Let's wr
small program and see how it works.

1. class booleanDataType{
2. public static void main(String args[]){
3. // Setting the values for boolean data type
4. boolean Java = true;
5. boolean Python = false;
6. System.out.println(Java); // Output will be true
7. System.out.println(Python); // Output will be false
8. }
9. }
Byte Data Type

The byte data type is an illustration of a primitive data type. It is a signed two's complement integer of 8 bits, and it st
whole numbers ranging from -128 to 127. A byte data type is useful for saving large amounts of memory. Let's wr
small program and see how it works.

1. class ByteExample {
2. public static void main(String[] args) {
3. byte n, a;
4. n = 127;
5. a=177;
6. System.out.println(n); // prints 127
7. System.out.println(a); // throws an error because it cannot store more than 127 bits
8. }
9. }
Char Data Type

A single character is stored in this data type, and the character must be enclosed in single quotes, such as 'E' or 'e'. You
also use ASCII values to display specific characters. Let's look at a simple example to see how it works.

1. public class PrimitiveDataType{

2. public static void main(String[] args) {
3. //storing a single character
4. char alpha = 'J';
5. //storing the ASCII of the respective character or alphabets
6. char a = 65;
7. char b = 66,
8. char c = 67;
9. System.out.println(alpha); // prints J
10. System.out.println(a); // Displays 65
11. System.out.println(b); // Displays 66
12. System.out.println(c); // Displays 67
13.
14. }//end of main function
15. }//end of PrimitiveDataType class
 Short Data Type

A short data type is larger than a byte but smaller than an integer, and it saves values ranging from -32,768 to 32767.
data type's default size is 2 bytes. Let's look at an example to understand the short data type better.

1. public class PrimitiveDataType{

2. public static void main(String[] args) {
3. short n= 3435,
4. System.out.println(n); // prints the value present in n i.e. 3435
5.
6. }//end of main function
7. }//end of PrimitiveDataType class
Int Data Type

This data type is capable of storing whole numbers ranging from -2147483648 to 2147483647. When creating varia
with numeric values, int is generally the preferred data type.

1. public class PrimitiveDataType{

2. public static void main(String[] args) {
3. int num = 5464564;
4. System.out.println(num); // prints 5464564
5. }//end of main function
6. }//end of PrimitiveDataType class
Long Data Type

This data type is a two's complement 64-bit integer. A long data type's default size is 64 bits, and its value ranges fr
263 to 263-1.

1. public class PrimitiveDataType{

2. public static void main(String[] args) {
3. // a variable named num of long is created to store the long value
4. long num = 15000000000L;
5. // The output of the below System.out.println will print 15000000000 that is the value stored in num
6. System.out.println(num);
7. // a variable named num1 of long is created to store the long value
8. long num1 = 897155L;
9. // The output of the below System.out.println will print 897155 that is the value stored in num1
10. System.out.println(num);
11. }//end of main function
12. }//end of PrimitiveDataType class
Float Data Type

It would be best to use a floating-point type when you need a number with a decimal, such as 8.88 or 3.14515.

This data type supports fractional numbers ranging from 3.4e038 to 3.4e+038. It is important to note that the value sh
end with an "f." Let's look at a specific example to understand this data type better.

1. public class PrimitiveDataType{

2. public static void main(String[] args) {
3. // a variable named num of float type is created to store the float value
4. float num =67;
5. // The output of the below System.out.println will print 897155 that is the value stored in num
6. System.out.println(num); // prints the floating number value
7. }//end of main function
8. }//end of PrimitiveDataType class
Double Data Type

The double data type can store fractional numbers from 1.7e-308 to 1.7e+308. Note that you should end the value w
"d":

1. public class PrimitiveDataType{

2. public static void main(String[] args) {
3. // a variable named num of double type is created to store the double value
4. double num = 79.678d;
5. // The output of the below System.out.println will print 79.678 that is the value stored in num
6. System.out.println(num); // prints the double number value
7. }//end of main function
8. }//end of PrimitiveDataType class

Abstract Data Types (ADT)

What are ADTs?
Abstract Data Types (ADTs) are models for data structures that define data and operations without specifying the
implementation details. They provide a theoretical framework for data manipulation.

Examples of ADTs
 List ADT: Collection of elements with operations to insert, delete, and access elements.
 Stack ADT: Collection of elements with LIFO access.
 Queue ADT: Collection of elements with FIFO access.

----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

List ADT

Lists are linear data structures that hold data in a non-continuous structure. The list is made up of data storage contain
known as "nodes." These nodes are linked to one another, which means that each node contains the address of anothe
block. All of the nodes are thus connected to one another via these links.
 Some of the most essential operations defined in List ADT are listed below.

 front(): returns the value of the node present at the front of the list.

 back(): returns the value of the node present at the back of the list.

 push_front(int val): creates a pointer with value = val and keeps this pointer to the front of the linked list.

 push_back(int val): creates a pointer with value = val and keeps this pointer to the back of the linked list.

 pop_front(): removes the front node from the list.

 pop_back(): removes the last node from the list.

 empty(): returns true if the list is empty, otherwise returns false.

 size(): returns the number of nodes that are present in the list.

Stack ADT
A stack is a linear data structure that only allows data to be accessed from the top. It simply has two operations: push
insert data to the top of the stack) and pop (to remove data from the stack). (used to remove data from the stack top).

Some of the most essential operations defined in Stack ADT are listed below.
 top(): returns the value of the node present at the top of the stack.

 push(int val): creates a node with value = val and puts it at the stack top.

 pop(): removes the node from the top of the stack.

 empty(): returns true if the stack is empty, otherwise returns false.

 size(): returns the number of nodes that are present in the stack.

Queue ADT

A queue is a linear data structure that allows data to be accessed from both ends. There are two main operations in the
queue: push (this operation inserts data to the back of the queue) and pop (this operation is used to remove data from
front of the queue).

Some of the most essential operations defined in Queue ADT are listed below.

 front(): returns the value of the node present at the front of the queue.

 back(): returns the value of the node present at the back of the queue.

 push(int val): creates a node with value = val and puts it at the front of the queue.

 pop(): removes the node from the rear of the queue.

 empty(): returns true if the queue is empty, otherwise returns false.

 size(): returns the number of nodes that are present in the queue.

Advantages of ADT in Data Structures

The advantages of ADT in Data Structures are:

 Provides abstraction, which simplifies the complexity of the data structure and allows users to focus on the
functionality.
 Enhances program modularity by allowing the data structure implementation to be separate from the rest of th
program.
 Enables code reusability as the same data structure can be used in multiple programs with the same interface.
 Promotes the concept of data hiding by encapsulating data and operations into a single unit, which enhances
security and control over the data.

 Supports polymorphism, which allows the same interface to be used with different underlying data structures, providi
flexibility and adaptability to changing requirements.

Disadvantages of ADT in Data Structures

 There are some potential disadvantages of ADT in Data Structures:

 Overhead: Using ADTs may result in additional overhead due to the need for abstraction and encapsulation.

 Limited control: ADTs can limit the level of control that a programmer has over the data structure, which can be a
disadvantage in certain scenarios.

 Performance impact: Depending on the specific implementation, the performance of an ADT may be lower than tha
a custom data structure designed for a specific application.

Introduction to algorithms, Importance of Algorithm Analysis, characteristics of algorithms

Introduction to Algorithms
What are Algorithms?
Algorithms are step-by-step procedures or formulas for solving problems. They are a sequence of computational steps
that transform the input into the output.

Importance of Algorithm Analysis

Efficiency: Determines the performance of an algorithm.
Optimization: Helps in improving the algorithm to use fewer resources.
Scalability: Ensures the algorithm can handle large inputs efficiently.
Characteristics of Algorithms
Correctness: Produces the correct output for all possible inputs.
Efficiency: Uses the least amount of resources (time and space).
Finiteness: Terminates after a finite number of steps.
Definiteness: Each step is clearly and unambiguously defined.
Input/Output: Takes input and produces output.

----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----*----

The word Algorithm means ” A set of finite rules or instructions to be followed in calculations or other problem-solv
operations ”
Or
” A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive
operations”.

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some of the key areas where algorithms
used include:

 Computer Science: Algorithms form the basis of computer programming and are used to solve problems rangi
from simple sorting and searching to complex tasks such as artificial intelligence and machine learning.
  Mathematics: Algorithms are used to solve mathematical problems, such as finding the optimal solution to a
system of linear equations or finding the shortest path in a graph.
 Operations Research: Algorithms are used to optimize and make decisions in fields such as transportation,
logistics, and resource allocation.
 Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine learning, and are u
to develop intelligent systems that can perform tasks such as image recognition, natural language processing,
decision-making.
 Data Science: Algorithms are used to analyze, process, and extract insights from large amounts of data in field
such as marketing, finance, and healthcare.

What is the need for algorithms?

 Algorithms are necessary for solving complex problems efficiently and effectively.
 They help to automate processes and make them more reliable, faster, and easier to perform.
 Algorithms also enable computers to perform tasks that would be difficult or impossible for humans to do
manually.
 They are used in various fields such as mathematics, computer science, engineering, finance, and many others
optimize processes, analyze data, make predictions, and provide solutions to problems

it must have the following characteristics:

Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should be clear in all aspects and m
lead to only one meaning.
Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs. It may or may not take inpu
Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined a
well. It should produce at least 1 output.
Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
Feasible: The algorithm must be simple, generic, and practical, such that it can be executed with the available resourc
It must not contain some future technology or anything.
Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions
can be implemented in any language, and yet the output will be the same, as expected.
Input: An algorithm has zero or more inputs. Each that contains a fundamental operator must accept zero or more inp
Output: An algorithm produces at least one output. Every instruction that contains a fundamental operator must accep
zero or more inputs.
Definiteness: All instructions in an algorithm must be unambiguous, precise, and easy to interpret. By referring to any
the instructions in an algorithm one can clearly understand what is to be done. Every fundamental operator in instruct
must be defined without any ambiguity.
Finiteness: An algorithm must terminate after a finite number of steps in all test cases. Every instruction which contai
fundamental operator must be terminated within a finite amount of time. Infinite loops or recursive functions without
base conditions do not possess finiteness.
Effectiveness: An algorithm must be developed by using very basic, simple, and feasible operations so that one can tr
it out by using just paper and pencil.
Properties of Algorithm:
 It should terminate after a finite time.
 It should produce at least one output.
 It should take zero or more input.
 It should be deterministic means giving the same output for the same input case.
Every step in the algorithm must be effective i.e. every step should do some work.
Types of Algorithms:
There are several types of algorithms available. Some important algorithms are:

1. Brute Force Algorithm:

It is the simplest approach to a problem. A brute force algorithm is the first approach that comes to finding when we s
problem.

2. Recursive Algorithm:
A recursive algorithm is based on recursion. In this case, a problem is broken into several sub-parts and called the sam
function again and again.

3. Backtracking Algorithm:
The backtracking algorithm builds the solution by searching among all possible solutions. Using this algorithm, we ke
on building the solution following criteria. Whenever a solution fails we trace back to the failure point build on the ne
solution and continue this process till we find the solution or all possible solutions are looked after.

4. Searching Algorithm:
Searching algorithms are the ones that are used for searching elements or groups of elements from a particular data
structure. They can be of different types based on their approach or the data structure in which the element should be
found.

5. Sorting Algorithm:
Sorting is arranging a group of data in a particular manner according to the requirement. The algorithms which help in
performing this function are called sorting algorithms. Generally sorting algorithms are used to sort groups of data in
increasing or decreasing manner.

6. Hashing Algorithm:
Hashing algorithms work similarly to the searching algorithm. But they contain an index with a key ID. In hashing, a
is assigned to specific data.

7. Divide and Conquer Algorithm:

This algorithm breaks a problem into sub-problems, solves a single sub-problem, and merges the solutions to get the
solution. It consists of the following three steps:

Divide
Solve
Combine
8. Greedy Algorithm:
In this type of algorithm, the solution is built part by part. The solution for the next part is built based on the immedia
benefit of the next part. The one solution that gives the most benefit will be chosen as the solution for the next part.
9. Dynamic Programming Algorithm:
This algorithm uses the concept of using the already found solution to avoid repetitive calculation of the same part of
problem. It divides the problem into smaller overlapping subproblems and solves them.

10. Randomized Algorithm:

In the randomized algorithm, we use a random number so it gives immediate benefit. The random number helps in
deciding the expected outcome

Advantages of Algorithms:
 It is easy to understand.
 An algorithm is a step-wise representation of a solution to a given problem.
 In an Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programme
convert it into an actual program.
Disadvantages of Algorithms:
 Writing an algorithm takes a long time so it is time-consuming.
 Understanding complex logic through algorithms can be very difficult.
 Branching and Looping statements are difficult to show in Algorithms(imp).
How to Design an Algorithm?
To write an algorithm, the following things are needed as a pre-requisite:
 The problem that is to be solved by this algorithm i.e. clear problem definition.
 The constraints of the problem must be considered while solving the problem.
 The input to be taken to solve the problem.
 The output is to be expected when the problem is solved.
 The solution to this problem is within the given constraints

algorithm design tools: pseudo code and flowchart, relationship among data
Algorithm, Pseudocode, Programs, and Flowcharts
Algorithm: An algorithm is a step-by-step procedure for solving a computational problem. It is a process or set of rul
be followed in calculations or other problem-solving operations.
Program: A program is a step-by-step machine instruction used for solving any problem or computational task

Difference between Algorithm and Program

Programs have been written recently but Algorithms have appeared for centuries. As a common practice, mathematic
or scientists have been devising procedures for solving computational problems. Those working on problems were gi
solutions in form of step-by-step procedures known as algorithms. Now we want that same procedure must be followe
machines so we are writing programs.
An algorithm basically means how to solve a problem. First, we need to learn a few analytical or problem-solving skil
write an algorithm.
Example:
1. Let’s consider a chef who knows how to prepare a dish then he/she can easily prepare the recipe of that dish.
2. Let’s consider a chemist who is well versed with different chemical reactions then he/she can easily prepa
chemical formula applying those reactions.
Once an algorithm is prepared, we need to convert it into a Program so that the computer can execute it and perform
computational task. Any programming language can be used to write a program but it must strictly follow the synta
that programming language.
What is Pseudocode?
Pseudocode is an artificial and informal language that helps programmers in developing algorithms. It is basically a “
based” detail (algorithmic) design tool.
Algorithm and Program Example:
So here I have an example algorithm as well as a C++ program that is not a complete program is just a function.

Let us Understand the Algorithm.

The Algorithm is for finding the average of the list of elements. That is, we have a collection of elements and we wa
find out the average. First, we assign 0 to Sum. Then for each element x in the list, we begin sum assigned sum+ x
adding each value of x into the sum variable. Then after that, the average is assigned sum by the number of elements,
then, return the average. So, if you read the above algorithm, you can understand how to find the average of a li
elements. Add all of them and divide by the number of elements. That’s it. This is how we write our algorithm u
pseudocode.
Let us Understand the Program.
Now the same thing for finding the average list of elements, we have written the program using C++ language. I
function, it’s not a complete program, just a function inside a program. If we don’t use a semicolon to end the statem
it’s an error, and instead of assignment if we write less than or a hyphen symbol, then also it is an error. So, if you wa
store the value then you must use an equal symbol and that is called an assignment.
So, it means you should follow the proper syntax of a language. Because this is not for you. You are writing the prog
for the compiler to understand and convert it into machine code. You will write a C++ program and that gets conve
into machine code or machine language. So, you are actually talking to the compiler. You should talk in such a way
you can easily understand.
If the compiler is not understanding your program, then the compiler cannot convert your program into machine code
you should follow the syntax perfectly. That is the reason you have to put some little extra effort into learning programm
What is a Flowchart?
A flowchart is used for showing the flow of control in a program and the sequence of steps involved in a hierarch
manner. It is basically a diagrammatic representation of an algorithm, workflow, or process.
So, if a program is very big then it is very difficult to figure out how the flow of the program is, Flow charts are usefu
understanding the program, instead of one is reading the program and understanding it, he can see the flow chart
understand how the program is working.
It is just like if you talk about electrical wiring in a home. Then from where the wires or the cables are moving through
walls. If you have a plan then you can know where exactly they are flowing and where the important points are, everyt
you can know. Otherwise, if there is any problem with the wiring, then you have to dig the whole wall to find ou
problem. If there is a proper plan then you can understand. So before laying the wire or pulling the wires we will ma
plan. In the same way, before writing the program we make a flowchart. So based on the flow chart we will write
program. This will help us to understand the program.
Use of Flowchart
Flowcharts were highly used at the times of Monolithic Programming. Then later on when the concept of Proced
Programming came into practice, the usage of flowcharts was a little reduced.
Steps in the flowchart:
Usually, when we are using a flow chart for the program, it consists of three steps:
1. Input
2. Process
3. Output
We will call it like this. First, it takes some input. Then it will process. Then it will give the output. So, any procedure
take will have similar steps. For example, preparing a dish. Input is the ingredients. That process is the process of ma
a dish and the output is the dish ready. If you take a chemistry experiment that is done usually in laboratories will
input means chemicals and the vessels or instruments whatever you need. Then the process of what you will do with
and then it gets done successfully. So, every procedure will have these 3 things and the program is also used to look
this.
Elements of Flowchart:
Now let us look at the elements of the flow chart. The following image shows the different elements of a flowchart.
Terminal

The terminal is an oval that indicates the beginning and end of a program. It usually contains the words Start or End.
Flowline
The flowline is a line from one symbol pointing towards another to show the process’s order of operation. This displa
the flow of execution in a program.

Input/Output
Input/output is represented by a rhomboid and indicates the input or output of data. This is similar to setting a value to
variable.

Process
A process, represented by a rectangle, is an operation that manipulates data. Think of this as changing the value of a
number-based variable using an operator such as +.

Decision
Decisions are represented by a rhombus and show a conditional operation that will determine which path a program
should take. This is similar to conditional statements which control the flow of execution in a program
Flowchart for adding two numbers

. No Algorithm Flowchart

An algorithm is a step-by-step A flowchart is a diagram created with different

1. procedure to solve a problem. shapes to show the flow of data.

The algorithm is complex to

2. understand. A flowchart is easy to understand.

3. In the algorithm, plain text is used. In the flowchart, symbols/shapes are used.

4. The algorithm is easy to debug. A flowchart is hard to debug.

The algorithm is difficult to

5. construct. A flowchart is simple to construct.

The algorithm does not follow any

6. rules. The flowchart follows rules to be constructed.

The algorithm is the pseudo-code for A flowchart is just a graphical representation of

7. the program. that logic.

Difference between Algorithm and

Pseudocode
Algorithm Pseudocode
An Algorithm is used to provide a solution to a A Pseudocode is a step-by-step description of an
particular problem in form of a well-defined algorithm in code-like structure using plain English
step-based form. text.
Pseudocode also uses reserved keywords like if-else,
An algorithm only uses simple English words
for, while, etc.
 These are a sequence of steps of a solution to a These are fake codes as the word pseudo means
problem fake, using code like structure and plain English text

There are no rules to writing algorithms There are certain rules for writing pseudocode
Algorithms can be considered pseudocode Pseudocode cannot be considered an algorithm
It is difficult to understand and interpret It is easy to understand and interpret

Difference between Flowchart and Pseudocode

Flowchart Pseudocode
A Pseudocode is a step-by-step description of an
A Flowchart is pictorial representation of flow
algorithm in code like structure using plain English
of an algorithm.
text.
A Flowchart uses standard symbols for input,
output decisions and start stop statements. Pseudocode uses reserved keywords like if-else, for,
Only uses different shapes like box, circle and while, etc.
arrow.
This is a way of visually representing data,
These are fake codes as the word pseudo means
these are nothing but the graphical
fake, using code like structure but plain English text
representation of the algorithm for a better
instead of programming language
understanding of the code
Pseudocode is better suited for the purpose of
Flowcharts are good for documentation
understanding

ADVANTAGES OF USING FLOWCHARTS

The benefits of flowcharts are as follows:
1. Communication: Flowcharts are better way of communicating the logic of a system to all concerned.
2. Effective analysis: With the help of flowchart, problem can be analysed in more effective way.
Proper documentation: Program flowcharts serve as a good program documentation, which is needed for various
purposes.
4. Efficient Coding: The flowcharts act as a guide or blueprint during the systems analysis and program developmen
phase.
5. Proper Debugging: The flowchart helps in debugging process.

6. Efficient Program Maintenance: The maintenance of operating program becomes easy with the help of flowchart
helps the programmer to put efforts more efficiently on that part

Advantages:
· Logic Flowcharts are easy to understand.They provide a graphical representation of actions to be taken.
· Logic Flowcharts are well suited for representing logic where there is intermingling among many actions.
Disadvantages:
· Logic Flowcharts may encourage the use of GoTo statements leadingsoftware design that is unstructured with l
that is difficult to decipher.
· Without an automated tool, it is time-consuming to maintain Logic Flowcharts.
· Logic Flowcharts may be used during detailed logic design to specify a module.
· However, the presence of decision boxes may encourage the use of GoTo statements, resulting in software that
not structured. For this reason, Logic Flowcharts may be better used during Structural Design

LIMITATIONS OF USING FLOWCHARTS

1. Complex logic: Sometimes, the program logic is quite complicated. In that case, flowchart becomes complex and
clumsy.
2. Alterations and Modifications: If alterations are required the flowchart may require re-drawing completely.
3. Reproduction: As the flowchart symbols cannot be typed, reproduction of flowchart becomes a problem.
4. The essentials of what is done can easily be lost in the technical details of how it is done.

Pseudo Code
Pseudo code is a high-level description of an algorithm that uses the conventions of programming languages but with
strict syntax rules. It helps in understanding and planning algorithms before actual coding.

Characteristics of Pseudo Code

 Simplicity: Easy to understand.
 Clarity: Clearly represents the steps of the algorithm.
 Flexibility: Can be easily modified.

Example of Pseudo Code

plaintext
Copy code
Algorithm to find the largest number in a list:
1. Start
2. Initialize largest to the first element
3. For each element in the list
a. If the element is larger than largest
i. Set largest to the element
4. End

Progressing with pseudocode

Now that we have the entire algorithm thought out and in visual form, we can take steps to turn it into code. Some peo
may be able to jump right into a development environment and start hacking away, but let’s take it slow and create so
pseudocode first.

Pseudocode is a description of an algorithm using everyday wording, but molded to appear similar to a simplified
programming language.

To create pseudocode from what we have so far we can use the flowchart’s flowlines to guide the structure of our cod
we simplify the steps we outlined earlier:

define password
create a pass_length variable and set it to 0
create a contains_number variable and set it to False
if the entire password hasn't been searched:
iterate to the next character of the password
increment the pass_length variable
if the current character of the password contains number:
set contains_number to True
if pass_length is greater than 8 and if contain_number is equal to True:
valid password
otherwise:
invalid password
The final code
Now the closing moments! With pseudocode in hand, the algorithm can be programmed in any language. Here it is
in Python:

# 1. Input the `password` that we plan to validate

password = "c0decademy"
# 2. To keep track of the password length, establish a `pass_length` variable and initially set it to `0`
pass_length = 0
# 3. To keep track of if the password contains a number, establish a `contains_number` variable and initially set it to
`False`
contains_number = False
# 4. Has the entire `password` been searched?
while pass_length is not len(password):
# 5. Iterate to the next character in `password`
current_character = password[pass_length]
# 6. Increment `pass_length`
pass_length = pass_length + 1
# 7. Is the current character a number?
if current_character.isdigit():
# If so, set the `contains_number` variable to `True` and then go back to step 4
contains_number = True

# 8. Is the `pass_length` greater than `8` and is `contain_number` equal to `True`?

if pass_length > 8 and contains_number is True:
# If so, then the `password` is valid!
print("Valid Password!")
else:
# If not, then the `password` is invalid
print("Invalid Password")

Advantages of Pseudocode

 Improves the readability of any approach. It’s one of the best approaches to start implementation of an
algorithm.
 Acts as a bridge between the program and the algorithm or flowchart. Also works as a rough
documentation, so the program of one developer can be understood easily when a pseudo code is written
out. In industries, the approach of documentation is essential. And that’s where a pseudo-code proves v
 The main goal of a pseudo code is to explain what exactly each line of a program should do, hence maki
the code construction phase easier for the programmer.

Relationship Among Data

The relationship among data elements can be defined through their organization in data structures. Different data
structures model relationships in various ways:

Linear Relationships
 Arrays: Elements have a direct relationship, with each element being adjacent to the next.
 Linked Lists: Each element (node) points to the next, forming a chain.

Hierarchical Relationships
 Trees: Represent hierarchical relationships with a parent-child structure.
o Binary Tree: Each node has at most two children.
Network Relationships
 Graphs: Represent complex relationships where nodes (vertices) can be connected by edges in various ways.
o Directed Graph: Edges have directions.
o Undirected Graph: Edges do not have directions.

Example 1: C Programming Language – Sum of Two Numbers

Component Description
Problem Find the sum of two numbers (e.g., 5 and 3)
1. Start
2. Declare variables a, b, and sum
3. Assign values: a = 5, b = 3
4. Calculate sum = a + b
5. Display the sum
6. Stop

Algorithm

BEGIN
Pseudo Code
// Step 1: Declare variables
 DECLARE integer a, b, sum

// Step 2: Assign values

SET a = 5
SET b = 3

// Step 3: Perform addition

SET sum = a + b

// Step 4: Print result

DISPLAY "Sum = ", sum

END

#include <stdio.h>

int main() {
// Step 1: Declare variables
int a, b, sum;

// Step 2: Assign values to variables

a = 5;
b = 3;
Program (C)
// Step 3: Perform addition
sum = a + b;

// Step 4: Print the result

printf("Sum = %d\n", sum);

return 0;
}
Example 2: Python Programming Language – Sum of Two Numbers
Component Description
Problem Find the sum of two numbers (e.g., 10 and 7)

1. Start
2. Define variables a and b
3. Assign values: a = 10, b = 7
4. Compute sum = a + b
5. Print the result
6. End

Algorithm

BEGIN
# Step 1: Define variables
SET a = 10
Pseudo Code
SET b = 7

# Step 2: Add the numbers

 SET sum = a + b

# Step 3: Print the result

PRINT "Sum =", sum

END
# Step 1: Assign values to variables
a = 10
b=7
Program
# Step 2: Perform addition
(Python) sum = a + b

# Step 3: Print the result

print("Sum =", sum)

Explanation:

Step What Happens

Input Two numbers are taken from the user.
Processing The numbers are added using the addition operator (+).
Output The result (sum) is printed/displayed to the user.
Adaptation per Lang Input/output and declaration style match each language's standard approach.
 Upper Bound:
 Represents the maximum amount of time or space an algorithm will take to complete, given any input of a
certain size.
 Often expressed using Big O notation, which provides an asymptotic upper bound.
 For example, an algorithm with an upper bound of O(n) means its execution time will not grow faster than a
linear function of the input size 'n' in the worst-case scenario.

Lower Bound:
 Represents the minimum amount of time or space an algorithm must take to complete, given any input of a
certain size.
 Often expressed using Big Omega notation, which provides an asymptotic lower bound.
 For example, an algorithm with a lower bound of Ω(n log n) suggests that it cannot be solved faster than a
logarithmic-linear function in the best-case or average-case scenario.

In essence:
 The upper bound provides a guarantee on the maximum resource consumption, while the lower bound indica
the minimum resource usage.
 Knowing both the upper and lower bounds can help in selecting the most appropriate algorithm for a specific
task or in understanding the inherent limitations of solving a problem.

Complexity of an Algorithm, Asymptotic Analysis and Notations.

Complexity of an Algorithm

What is Complexity?
Complexity refers to the resources required by an algorithm, typically time and space. It measures how these resource
grow with the size of the input.
Types of Complexity
1. Time Complexity: The amount of time an algorithm takes to complete.
2. Space Complexity: The amount of memory an algorithm uses during its execution.
3. Best case complexity: The best-case scenario for an algorithm is the scenario in which the algorithm performs
minimum amount of work (e.g. takes the shortest amount of time, uses the least amount of memory, etc.).
4. Worst case complexity: The worst-case scenario for an algorithm is the scenario in which the algorithm perfor
the maximum amount of work (e.g. takes the longest amount of time, uses the most amount of memory, etc.).

Time Complexity
 Example: An algorithm with a time complexity of O(n) will take linear time relative to the input size.

Space Complexity
Example: An algorithm with a space complexity of O(n) will use linear memory relative to the input size.

Typical Algorithm Complexities

This table will explain what every type of complexity (running time) means:
Running
Complexity Description
Time
It takes a constant number of steps for performing a given operation (for
constant O(1) example 1, 5, 10 or other number) and this count does not depend on the size of
the input data.
It takes the order of log(N) steps, where the base of the logarithm is most often
2, for performing a given operation on N elements. For example, if N =
logarithmic O(log(N)) 1,000,000, an algorithm with a complexity O(log(N)) would do about 20 steps
(with a constant precision). Since the base of the logarithm is not of a vital
importance for the order of the operation count, it is usually omitted.
It takes nearly the same amount of steps as the number of elements for
performing an operation on N elements. For example, if we have 1,000 elements,
linear O(N) it takes about 1,000 steps. Linear complexity means that the number of elements
and the number of steps are linearly dependent, for example the number of steps
for N elements can be N/2 or 3*N.
It takes N*log(N) steps for performing a given operation on N elements. For
O(n*log(n))
example, if you have 1,000 elements, it will take about 10,000 steps.
It takes the order of N2 number of steps, where the N is the size of the input data,
for performing a given operation. For example if N = 100, it takes about 10,000
quadratic O(n2) steps. Actually we have a quadratic complexity when the number of steps is in
quadratic relation with the size of the input data. For example for N elements the
steps can be of the order of 3*N2/2.
It takes the order of N3 steps, where N is the size of the input data, for performing
3
cubic O(n ) an operation on N elements. For example, if we have 100 elements, it takes about
1,000,000 steps.
It takes a number of steps, which is with an exponential dependability with the
size of the input data, to perform an operation on N elements. For example, if N
O(2n), O(N!), = 10, the exponential function 2N has a value of 1024, if N = 20, it has a value of
exponential
O(nk), … 1 048 576, and if N = 100, it has a value of a number with about 30 digits. The
exponential function N! grows even faster: for N = 5 it has a value of 120, for N
= 10 it has a value of 3,628,800 and for N = 20 – 2,432,90,008,176,640,000.

Asymptotic Analysis and Notations

Asymptotic Analysis
Asymptotic analysis is used to describe the behavior of an algorithm as the input size grows. It provides a high-level
understanding of the algorithm's efficiency.

Asymptotic Notations
1. Big O Notation (O): Describes the upper bound of an algorithm's running time. It represents the worst-case
scenario.
o Example: O(n), O(log n), O(n^2).
2. Omega Notation (Ω): Describes the lower bound of an algorithm's running time. It represents the best-case
scenario.
o Example: Ω(n), Ω(log n), Ω(n^2).
3. Theta Notation (Θ): Describes the tight bound of an algorithm's running time. It represents both the best and
worst-case scenarios.
o Example: Θ(n), Θ(log n), Θ(n^2).

Big O Notation
 O(1): Constant time.
 O(n): Linear time.
 O(n^2): Quadratic time.

What are the Different Types of Asymptotic Notations?

Mainly there are three different types of asymptotic notations:
 Big O Notation
 Omega Notation
 Theta Notation
Now, we will discuss them one by one in complete detail.
Big-O Notation (O)
Big O notation is a mathematical concept used in computer science to describe the upper bound of an algorithm's time
space complexity. It provides a way to express the worst-case scenario of how an algorithm performs as the size of th
input increases.
Mathematical Representation of Big O Notation
A function f(n) is said to be O(g(n)) if there exist positive constants c 0 and c1 such that 0 ≤ f(n) ≤ c0*g(n) for all n ≥ c1
This means that for sufficiently large values of n, the function f(n) does not grow faster than g(n) up to a constant fact

O(g(n)) = {f(n): there exist positive constants c0 and c1 such that 0 ≤ f(n) ≤ c0g(n) for all n ≥ c1}.
For Example:
Let, f(n) = n2 + n + 1
g(n) = n2
n2 + n + 1 <= c (n2)
The time complexity of the above function is O(n2 ), because the above function has to run for n2 time at least.
Omega Notation(Ω)
Omega notation is used to denote the lower bound of the algorithm; it represents the minimum running time of an
algorithm. Therefore, it provides the best-case complexity of any algorithm.

Ω(g(n)) = {f(n): there exist positive constants c0 and c1, such that 0 ≤ c0g(n) ≤ f(n) for all n ≥ c1}.
For Example:
Let,
 f(n) = n2 + n
Then, the best-case time complexity will be Ω(n2)
 f(n) = 100n + log(n)

Then, the best-case time complexity will be Ω(n).

Theta Notation(θ)
Theta notation is used to denote the average bound of the algorithm; it bounds a function from above and below, that’
why it is used to represent exact asymptotic behaviour.

Θ(g(n)) = {f(n): there exist positive constants c0, c1 and c2, such that 0 ≤ c0g(n) ≤ f(n) ≤ c1g(n) for all n ≥ c2}
Difference Between Big O Notation, Omega Notation, and Theta Notation
Parameter Big O Notation (O) Omega Notation (Ω) Theta Notation (Θ)

Describes an upper bound Describes a lower

Describes both an upper and a
on the time or space bound on the time or
Definition lower bound on the time or
complexity of an space complexity of an
space complexity.
algorithm. algorithm.

Used to characterize the Used to characterize Used to characterize an

Purpose worst-case scenario of an the best-case scenario algorithm's precise bound (both
algorithm. of an algorithm. worst and best cases).
 Indicates the maximum Indicates the minimum Indicates the exact rate of
Interpretation rate of growth of the rate of growth of the growth of the algorithm's
algorithm's complexity. algorithm's complexity. complexity.

f(n) = O(g(n)) if ∃ f(n) = Ω(g(n)) if ∃

f(n) = Θ(g(n)) if ∃ constants c₁,
Mathematical constants c > 0, n₀ such constants c > 0, n₀ such
c₂ > 0, n₀ such that 0 ≤ c₁g(n) ≤
Expression that 0 ≤ f(n) ≤ c*g(n) for that 0 ≤ c*g(n) ≤ f(n)
f(n) ≤ c₂g(n) for all n ≥ n₀.
all n ≥ n₀. for all n ≥ n₀.

Focuses on the lower

Focuses on the upper limit Focuses on both the upper and
limit of performance
Focus of performance (less lower limits, providing a
(more efficient
efficient aspects). balanced view of performance.
aspects).

It is commonly used to
Usage in Used to demonstrate Used to provide a precise
analyze efficiency,
Algorithm the effectiveness under analysis of algorithm efficiency
especially concerning
Analysis optimal conditions. in typical scenarios.
worst-case performance.

It is less common than Used when an algorithm

Predominant in theoretical
Common Big O but important for exhibits a consistent
and practical applications
Usage understanding best- performance across different
for worst-case analysis.
case efficiency. inputs.

Linear search in a sorted array,

Searching in an unsorted Inserting an element in
Examples where the element is always in
list: O(n). a sorted array: Ω(1).
the middle: Θ(n).