UNIT-1

Introduction to Analysis of Algorithms:-

Algorithm analysis is an important part of computational complexity theory, which
provides theoretical estimation for the required resources of an algorithm to solve a specific
computational problem. Most algorithms are designed to work with inputs of arbitrary length.
Analysis of algorithms is the determination of the amount of time and space resources
requiredto execute it.
The efficiency or running time of an algorithm is stated as a function relating the input
length to the number of steps, known as time complexity, or volume of memory, known
as space complexity.

Types of analysis:-
Worst-case − The maximum number of steps taken on any instance of size a.
Best-case − The minimum number of steps taken on any instance of size a.
Average case − An average number of steps taken on any instance of size a.
Amortized − A sequence of operations applied to the input of size a averaged over
time.
Importance of Algorithm Analysis:-
In the analysis of the algorithm, it generally focused on CPU (time) usage, Memory
usage, Disk usage, and Network usage. All are important, but the most concern is about the
CPU time. Be careful to differentiate between:
Performance: How much time/memory/disk/etc. is used when a program is run.
Thisdepends on the machine, compiler, etc. as well as the code we write.
Complexity: How do the resource requirements of a program or algorithm scale, i.e.
whathappens as the size of the problem being solved by the code gets larger.
Role of Algorithms in Computing:-
Algorithms play a crucial role in computing by providing a set of instructions for a
computer to perform a specific task. They are used to solve problems and carry out tasks in
computer systems, such as sorting data, searching for information, image processing, and
much more. An algorithm defines the steps necessary to produce the desired outcome, and
the computer follows the instructions to complete the task efficiently and accurately. The
development of efficient algorithms is a central area of computer science and has significant
impacts in various fields, from cryptography and finance to machine learning and robotics.
Algorithms are widely used in various industrial areas to improve efficiency, accuracy,
anddecision-making. Some of the key applications include:
1. Manufacturing: Algorithms are used to optimize production processes and supply
chainmanagement, reducing waste and increasing efficiency.
2. Finance: Algorithms are used to analyze financial data and make predictions, enabling
tradersand investors to make informed decisions.

3. Healthcare: Algorithms are used to process and analyze medical images, assist in
diagnosing diseases, and optimize treatment plans.4Retail: Algorithms are used for customer
relationship management, personalized product recommendations, and pricing optimization.

4. Transportation: Algorithms are used to optimize routes for delivery and transportation,
reducing fuel consumption and increasing delivery speed.

5. Energy: Algorithms are used to optimize energy generation, distribution, and

consumption, reducing waste and increasing efficiency.

6. Security: Algorithms are used to detect and prevent security threats, such as hacking, fraud,
and cyber-attacks.

In these and many other industries, algorithms play a crucial role in automating tasks,
improving decision-making, and enhancing overall performance and efficiency. Algorithms
are fundamental to computing and play a crucial role in many aspects of the field. Some of
the key needs and applications of algorithms in computing include:

1. Data processing: Algorithms are used to process and analyze large amounts of data, such
as sorting and searching algorithms.

2. Problem solving: Algorithms are used to solve computational problems, such as

mathematicalproblems, optimization problems, and decision-making problems.

3. Computer graphics: Algorithms are used to create and process images and graphics, such
as image compression algorithms and computer-generated graphics algorithms.

4. Artificial Intelligence: Algorithms are used to develop intelligent systems, such as

machine learning algorithms, natural language processing algorithms, and computer vision
algorithms.

5. Database management: Algorithms are used to manage and organize large amounts of
data indatabases, such as indexing algorithms and query optimization algorithms.

6. Network communication: Algorithms are used for efficient communication and data
transfer in networks, such as routing algorithms and error correction algorithms.

7. Operating systems: Algorithms are used in operating systems for tasks such as process
scheduling, memory management, and disk management.
 Algorithm of Efficiency:-

1. Space efficiency - the memory required, also called, space complexity

2. Time efficiency - the time required, also called time complexity
Space Efficiency:-

There are some circumstances where the space/memory used must be analyzed. Forexample, for
large quantities of data or for embedded systems programming.

Components of space/memory use:

Affected by: the compiler, compiler options, target

1. instruction space computer(cpu)

Affected by: the data size/dynamically allocated memory, static

2. data space program variables,

Affected by: the compiler, run-time function calls and

3. run-time stack space recursion,local variables, parameters

The space requirement has fixed/static/compile time and a variable/dynamic/runtime components.

Fixed components are the machine language instructions and static variables. Variable
components are the runtime stack usage and dynamically allocatedmemory usage.
Time Efficiency:-

Clearly the more quickly a program/function accomplishes its task the better.

The actual running time depends on many factors:

 The speed of the computer: cpu (not just clock speed), I/O, etc.
 The compiler, compiler options .
 The quantity of data - ex. search a long list or short.
 The actual data - ex. in the sequential search if the name is first or last.
Asymptotic Notations
In mathematics, asymptotic analysis, also known as asymptotics, is a method of describing
the limiting behavior of a function. In computing, asymptotic analysis of an algorithm refers to
defining the mathematical boundation of its run-time performance based on the input size. For
example, the running time of one operation is computed as f(n), and maybe for another operation, it
is computed as g(n2). This means the first operation running time will increase linearly with the
increase in n and the running time of the second operation will increase exponentially when n
increases. Similarly, the running time of both operations will be nearly the same if n is small in
value.
Usually, the analysis of an algorithm is done based on three cases:
1. Best Case (Omega Notation (Ω))
2. Average Case (Theta Notation (Θ))
3. Worst Case (O Notation(O))
All of these notations are discussed below in detail:
Omega (Ω) Notation:

Omega (Ω) notation specifies the asymptotic lower bound for a function f(n). For a given function
g(n), Ω(g(n)) is denoted by:

Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ c*g(n) ≤ f(n) for all n ≥ n0}.

This means that, f(n) = Ω(g(n)), If there are positive constants n0 and c such that, to the right of n0
the f(n) always lies on or above c*g(n).

Theta (Θ) Notation:

Big-Theta(Θ) notation specifies a bound for a function f(n). For a given function g(n), Θ(g(n)) is
denoted by:
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1*g(n) ≤ f(n) ≤ c2*g(n)
for all n ≥ n0}.

This means that, f(n) = Θ(g(n)), If there are positive constants n0 and c such that, to the right of n0
the f(n) always lies on or above c1*g(n) and below c2*g(n).

Big – O Notation:

Big – O (O) notation specifies the asymptotic upper bound for a function f(n). For a given function
g(n), O(g(n)) is denoted by:

O (g(n)) = {f(n): there exist positive constants c and n0 such that f(n) ≤ c*g(n) for all n ≥ n0}.

This means that, f(n) = O(g(n)), If there are positive constants n0 and c such that, to the right of n0
the f(n) always lies on or below c*g(n).

AVL Tree Data Structure

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference
between heights of left and right subtrees for any node cannot be more than one.

The difference between the heights of the left subtree and the right subtree for any node is known as
the balance factor of the node.

The AVL tree is named after its inventors, Georgy Adelson-Velsky and Evgenii Landis, who
published it in their 1962 paper “An algorithm for the organization of information”.
Example of AVL Trees:

The above tree is AVL because the differences between the heights of left and right subtrees for
every node are less than or equal to 1.
Operations on an AVL Tree:
1. Insertion
2. Deletion
3. Searching [It is similar to performing a search in BST]
Rotating the subtrees in an AVL Tree:
An AVL tree may rotate in one of the following four ways to keep itself balanced:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree gets out of
balance, we do a single left rotation.

Left-Rotation in AVL tree

Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get out of
balance, we do a single right rotation.

Right-Rotation in AVL Tree

Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place after that right
rotation executes.

Left-Right Rotation in AVL tree

Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place after that left
rotation executes.

Right-Left Rotation in AVL tree

Advantages of AVL Tree:

1. AVL trees can self-balance themselves and therefore provides time complexity as O(Log n)
for search, insert and delete.
2. It is a BST only (with balancing), so items can be traversed in sorted order.
3. Since the balancing rules are strict compared to Red Black Tree, AVL trees in general have
relatively less height and hence the search is faster.
4. AVL tree is relatively less complex to understand and implement compared to Red Black
Trees.
Disadvantages of AVL Tree:
1. It is difficult to implement compared to normal BST and easier compared to Red Black
2. Less used compared to Red-Black trees.
3. Due to its rather strict balance, AVL trees provide complicated insertion and removal
operations as more rotations are performed.
Applications of AVL Tree:
1. AVL Tree is used as a first example self balancing BST in teaching DSA as it is easier to
understand and implement compared to Red Black
2. Applications, where insertions and deletions are less common but frequent data lookups
along with other operations of BST like sorted traversal, floor, ceil, min and max.
3. Red Black tree is more commonly implemented in language libraries like map in C++, set in
C++, TreeMap in Java and TreeSet in Java.
4. AVL Trees can be used in a real time environment where predictable and consistent
performance is required.
// AVL tree implementation in C
#include <stdio.h>
#include <stdlib.h>
// Create Node
struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};

int max(int a, int b);

// Calculate height
int height(struct Node *N) {
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
// Create a node
struct Node *newNode(int key) {
struct Node *node = (struct Node *)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return (node);
}
// Right rotate
struct Node *rightRotate(struct Node *y) {
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
 return x;
}
// Left rotate
struct Node *leftRotate(struct Node *x) {
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}

// Get the balance factor

int getBalance(struct Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Insert node
struct Node *insertNode(struct Node *node, int key) {
// Find the correct position to insertNode the node and insertNode it
if (node == NULL)
return (newNode(key));
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
else
return node;

// Update the balance factor of each node and

// Balance the tree
node->height = 1 + max(height(node->left),
height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}

if (balance < -1 && key < node->right->key) {

node->right = rightRotate(node->right);
return leftRotate(node);
}
 return node;
}
struct Node *minValueNode(struct Node *node) {
struct Node *current = node;
while (current->left != NULL)
current = current->left;
return current;
}

// Delete a nodes
struct Node *deleteNode(struct Node *root, int key) {
// Find the node and delete it
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
if ((root->left == NULL) || (root->right == NULL)) {
struct Node *temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
struct Node *temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL)
return root;
// Update the balance factor of each node and
// balance the tree
root->height = 1 + max(height(root->left),
height(root->right));

int balance = getBalance(root);

if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}

if (balance < -1 && getBalance(root->right) <= 0)

return leftRotate(root);
 if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

// Print the tree

void printPreOrder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->key);
printPreOrder(root->left);
printPreOrder(root->right);
}
}
int main() {
struct Node *root = NULL;
root = insertNode(root, 2);
root = insertNode(root, 1);
root = insertNode(root, 7);
root = insertNode(root, 4);
root = insertNode(root, 5);
root = insertNode(root, 3);
root = insertNode(root, 8);
printPreOrder(root);
root = deleteNode(root, 3);
printf("\nAfter deletion: ");
printPreOrder(root);
return 0;
}

B-Tree
The B-tree is a self-balancing ordered structured data that stores data in a set of pages and
also allows efficient searching, insertion, and deletion operations. It has its origin in a generic form
of binary search trees developed by Rudolf Bayer and Edward M. McCreight in 1972. It is capable
of processing large datasets efficiently. Among database systems and file systems, B-trees are quite
often employed. This is so because they have a well-balanced structure, which allows for high speed
performance, and they can handle a great number of elements.

Representation of B-Tree in C
A B-tree is organized as a balanced tree with the following properties-

1. Each node of the data structure can contain several keys with pointers to their child nodes.
2. Balancing of nodes is done by applying limits key constraints on the maximum and
minimum number of keys a node can carry.
3. Each leaf is comparable to the next, thereby eliminating any queue or wait time.
Basic Operations on B-Tree
Search: Move down the tree repeatedly in a recursive way until a key is found.
Insertion: Put the key into a bunch of leaf nodes and split the nodes if it is necessary.
Deletion: Take away the leaves from the tree, join or split the nodes, if needed.
Time and Space Complexity:
1. Search: O(logN)
2. Insertion: O(logN)
3. Deletion: O(logN)

C Program to Implement B-Tree

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define M 4 // Maximum degree of the B-tree

struct BTreeNode {
int num_keys; // Number of keys currently in the node
int keys[M-1]; // Array of keys
struct BTreeNode *children[M]; // Array of child pointers
bool is_leaf; // True if node is a leaf
};

// Function to create a new node

struct BTreeNode *createNode(bool is_leaf) {
struct BTreeNode *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
if (newNode == NULL) {
perror("Memory allocation failed");
exit(EXIT_FAILURE);
}
newNode->num_keys = 0;
newNode->is_leaf = is_leaf;
for (int i = 0; i < M; i++) {
newNode->children[i] = NULL;
}
return newNode;
}

// Function to split a full child node

void splitChild(struct BTreeNode *parent, int index) {
struct BTreeNode *child = parent->children[index];
struct BTreeNode *newNode = createNode(child->is_leaf);

newNode->num_keys = M/2 - 1;

// Move keys and children to the new node

for (int i = 0; i < M/2 - 1; i++) {
newNode->keys[i] = child->keys[i + M/2];
}
 if (!child->is_leaf) {
for (int i = 0; i < M/2; i++) {
newNode->children[i] = child->children[i + M/2];
}
}

child->num_keys = M/2 - 1;

// Shift parent's children to make space for the new node

for (int i = parent->num_keys; i > index; i--) {
parent->children[i + 1] = parent->children[i];
}

parent->children[index + 1] = newNode;

// Shift parent's keys to insert the middle key from the child
for (int i = parent->num_keys - 1; i >= index; i--) {
parent->keys[i + 1] = parent->keys[i];
}

parent->keys[index] = child->keys[M/2 - 1];

parent->num_keys++;
}

// Function to insert a key into a non-full node

void insertNonFull(struct BTreeNode *node, int key) {
int i = node->num_keys - 1;

if (node->is_leaf) {
// Insert key into the sorted order
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->num_keys++;
} else {
// Find the child to insert the key
while (i >= 0 && node->keys[i] > key) {
i--;
}
i++;

if (node->children[i]->num_keys == M - 1) {
// Split child if it's full
splitChild(node, i);

// Determine which of the two children is the new one

if (node->keys[i] < key) {
i++;
}
 }
insertNonFull(node->children[i], key);
}
}

// Function to insert a key into the B-tree

void insert(struct BTreeNode **root, int key) {
struct BTreeNode *node = *root;

if (node == NULL) {
// Create a new root node
*root = createNode(true);
(*root)->keys[0] = key;
(*root)->num_keys = 1;
} else {
if (node->num_keys == M - 1) {
// Split the root if it's full
struct BTreeNode *new_root = createNode(false);
new_root->children[0] = node;
splitChild(new_root, 0);
*root = new_root;
}
insertNonFull(*root, key);
}
}

// Function to traverse and print the B-tree in-order

void traverse(struct BTreeNode *root) {
if (root != NULL) {
int i;
for (i = 0; i < root->num_keys; i++) {
traverse(root->children[i]);
printf("%d ", root->keys[i]);
}
traverse(root->children[i]);
}
}

// Main function to test B-tree implementation

int main() {
struct BTreeNode *root = NULL;

insert(&root, 10);
insert(&root, 20);
insert(&root, 5);
insert(&root, 6);
insert(&root, 12);
insert(&root, 30);

printf("In-order traversal of the B-tree: ");

traverse(root);
 printf("\n");

return 0;
}

Output:
In-order traversal of the B-tree: 5 6 10 12 20 30

Applications of B-Tree
Here are some applications of B-Tree-
1. Database indexing.
2. Filesystem management.
3. Metadata storage.
4. Caching mechanisms.
5. Multilevel indexing.