Page 1 of 20 OKYRAJKUMAR

OKYRAJKUMAR Since hardware speed varies, we do

not measure time in seconds.
We measure it in number of
UNIT – 1 operations, relative to input size n.

INTRODUCTION TO
ALGORITHMS AND 3. Time Complexity
ANALYSIS
Time complexity measures how the
running time increases with input
1. What is an Algorithm size n.
An algorithm is a finite, step-by-step Example:
procedure to solve a problem.
 A loop running n times → O(n)
Characteristics of a Good  A nested loop → O(n²)
Algorithm

1. Input: It may take zero or more

inputs. 4. Space Complexity
2. Output: It must produce at
least one output. Space complexity measures how
3. Definiteness: Every step must much memory an algorithm
be clear and unambiguous. requires.
4. Finiteness: It must terminate
after a finite number of steps. Memory is used in two parts:
5. Effectiveness: Steps must be
simple, basic, and executable. 1. Fixed Part: Variables,
constants, instructions
(independent of n)
2. Variable Part: Input-
2. Algorithm Analysis dependent memory (arrays,
recursion stack)
Algorithm Analysis tells us how
efficient an algorithm is in terms of: Example:

 Time (how fast it runs)  Array of size n → O(n) space

 Space (how much memory it  Simple variable → O(1) space
uses)
 Page 2 of 20 OKYRAJKUMAR

5. Asymptotic Notations 6. Common Orders of Growth

Asymptotic notations describe how Time

an algorithm grows when input size Complexi Name Meaning
becomes very large. ty
Time does not
O(1) Constant change with
(1) Big-O Notation – O(f(n)) size of n
Grows slowly
Logarithmi
 Represents upper bound O(log n) (Binary
c
 Shows worst-case performance Search)
Time
Example: O(n) Linear increases
Linear Search worst case → O(n) directly with n
Merge Sort,
O(n log Linearithm
Quick Sort
n) ic
(2) Omega Notation – Ω(f(n)) avg
O(n²) Quadratic Nested loops
 Represents lower bound Exponenti Subset/recursi
 Shows best-case performance O(2ⁿ)
al on problems
Brute force
Example: O(n!) Factorial
permutations
Linear Search best case → Ω(1)
These are extremely important for
exams and interviews.
(3) Theta Notation – Θ(f(n))

 Represents tight bound

 When both upper and lower 7. Algorithm Efficiency Cases
bounds are the same
Algorithms do not behave the same
Example: for every input.
Binary Search average case → Θ(log
1. Best Case
n)
The input that gives minimum
running time.
 Page 3 of 20 OKYRAJKUMAR

Example: Linear search finds element

at first index → Ω(1)

9. Analysis of Recursive Algorithms

2. Worst Case
Recursive algorithms are analyzed
The input that gives maximum using recurrence relations.
running time.
Example: Element not found → O(n)

3. Average Case Example: Factorial

Expected running time for random fact(n):

input. if n == 1:
Example: Element is in the middle → return 1
Θ(n) else:
return n * fact(n
- 1)

8. Analysis of Non-Recursive Recurrence:

Algorithms T(n) = T(n − 1) + O(1)
Solution: O(n)
Here we count loop iterations.

Example 1: Simple Loop

Example: Binary Search
for (i = 1; i <= n; i++)
print(i); T(n) = T(n/2) + O(1)

Runs n times → O(n) Solution: O(log n)

Because each step halves the input
size.

Example 2: Nested Loops

for (i = 1; i <= n; i++) Example: Merge Sort

for (j = 1; j <= n;
j++) T(n) = 2T(n/2) + O(n)
print(i, j);
Solution: O(n log n)
Runs n × n = n² times → O(n²)
 Page 4 of 20 OKYRAJKUMAR

⭐Summary
UNIT – 2
 Algorithm → Stepwise
procedure LINEAR DATA
 Time & Space Complexity → STRUCTURES
Measures of performance
 Asymptotic notations → O, Ω,
Θ 1. ARRAYS
 Orders of Growth → O(1) to
O(n!) 1.1 One-Dimensional Array (1D
 Efficiency → Best, Worst, Array)
Average case
 Non-recursive → Loop An array is a linear data structure
counting that stores multiple elements of the
 Recursive → Recurrence same data type in contiguous
relations memory.

Basic Operations

 Traversal → O(n)
 Insertion at end → O(1)
 Insertion at position → O(n)
 Deletion → O(n)
 Searching → O(n)

1.2 Two-Dimensional Array (2D

Array / Matrix)

2D array represents data in rows and

columns.

Example:

int a[3][3];

Applications

 Matrix operations
 Image processing
 Page 5 of 20 OKYRAJKUMAR

 Graph adjacency matrix  Operand → add to output

 ( → push to stack
 ) → pop until (
 Operator → pop operators of
2. STACK higher or equal precedence,
then push current operator
A stack is a LIFO (Last In First
Out) structure. Precedence Order:
Last inserted element is the first to be
removed. 1. ^
2. *, /
Basic Operations
3. +, -
 push(x)
 pop()
 peek()
3.3 Infix to Prefix Conversion
 isEmpty()
 isFull() Steps:
Time complexity: O(1) for push/pop. 1. Reverse the infix expression
2. Swap brackets ( ↔ )
3. Convert reversed infix →
postfix
3. APPLICATIONS OF STACK
4. Reverse postfix → prefix
3.1 Postfix Expression Evaluation

Algorithm:
3.4 Tower of Hanoi (Recursive,
1. Scan the expression left to right Stack Concept)
2. If operand → push into stack
3. If operator → pop last two Rules:
operands
 Move only one disk at a time
4. Evaluate and push result back
 Larger disk cannot be placed on
5. Final result remains in stack
a smaller one

Minimum Moves = 2ⁿ − 1
3.2 Infix to Postfix Conversion Recursive algorithm:
Rules: TOH(n, A, B, C):
 Page 6 of 20 OKYRAJKUMAR

TOH(n-1, A, C, B) 5.2 Double Ended Queue (Deque)

Move disk n from A to
C Insertion and deletion can occur from
TOH(n-1, B, A, C) both ends.

Types:
4. QUEUE
 Input restricted deque
A queue is a FIFO (First In First  Output restricted deque
Out) data structure.

Basic Operations
5.3 Priority Queue (Array
 enqueue(x) → Insert Implementation)
 dequeue() → Remove
 front(), rear() Each element has a priority.
Deletion always removes highest (or
Time complexity: O(1) lowest) priority element.

Array implementation:

5. TYPES OF QUEUES  Insert at end

 Find highest priority → delete
5.1 Circular Queue (O(n))

Overcomes the “false overflow”

problem of linear queues.
6. LINKED LIST
Rear update:
A linked list is a dynamic data
rear = (rear + 1) % size structure made of nodes.

Front update: Node Structure

front = (front + 1) % struct Node {

size int data;
Node* next;
};
 Page 7 of 20 OKYRAJKUMAR

6.1 Singly Linked List Advantages

Each node has:  Continuous traversal

 No NULL at end
 data
 next pointer

Operations 7. APPLICATION:
POLYNOMIAL
 Insert (begin, end, position) ADDITION/SUBTRACTION
 Delete USING LINKED LIST
 Traverse
A polynomial term is stored as a node
Time complexity for search/position with:
insert → O(n)
 coefficient
 power
 pointer
6.2 Doubly Linked List
Algorithm for Polynomial Addition
Each node has:
1. Traverse both polynomials
 data 2. If powers are equal → add
 prev pointer coefficients
 next pointer 3. If power of P1 > P2 → add P1
term to result
Advantages 4. If power of P2 > P1 → add P2
term to result
 Bidirectional traversal
5. Append remaining terms
 Faster deletion (because of prev
pointer) Time Complexity: O(m + n)
Disadvantages

 Extra memory required

⭐ EXAM SUMMARY

 Arrays → contiguous memory

6.3 Circular Linked List  Stack → LIFO, infix-postfix-
prefix, Tower of Hanoi
Last node’s next pointer points back  Queue → FIFO, circular queue,
to first node. deque, priority queue
 Page 8 of 20 OKYRAJKUMAR

 Linked lists → singly, doubly, 2. Bubble Sort

circular
 Applications → polynomial Bubble Sort repeatedly compares
operations adjacent elements and swaps them if
they are in the wrong order.

Time Complexity
UNIT – 3  Best: O(n)
 Worst: O(n²)
SORTING & SEARCHING  Average: O(n²)
TECHNIQUES
Stability

✔ Stable
1. Basic Concepts of Sorting

Sorting means arranging data in a

specific order (ascending or 3. Insertion Sort
descending).
Insertion Sort divides the list into
Why Sorting is Important? sorted and unsorted parts.
Each new element is inserted into its
 Improves searching
correct position in the sorted part.
performance
 Makes data analysis easier Time Complexity
 Used in many algorithms
(binary search, merge  Best: O(n)
operations)  Worst: O(n²)
 Average: O(n²)
Types of Sorting
Stability
1. Internal Sorting – Data fits in
main memory ✔ Stable
2. External Sorting – Data is
larger than memory; stored on
disk
o Example: External
Merge Sort
 Page 9 of 20 OKYRAJKUMAR

4. Selection Sort ❌ Unstable

Find the minimum element from the
unsorted part and place it at the
correct position. 6. Shell Sort
Time Complexity Shell Sort is an improved version of
Insertion Sort that uses a gap
 Best = O(n²) sequence.
 Worst = O(n²)
 Average = O(n²) Steps
Stability 1. Start with a large gap
2. Perform insertion sort on
❌ Unstable elements separated by the gap
3. Reduce gap to 1 and apply final
insertion sort

5. Quick Sort Time Complexity

Quick Sort uses Divide and Conquer  Typically O(n log n)
by selecting a pivot element.  Worst: O(n²)

Stability

❌ Unstable
Steps

1. Choose pivot
7. Heap Sort
2. Partition array into left
(smaller) and right (greater) Heap Sort uses a Binary Heap (Max-
3. Recursively apply Quick Sort Heap).
Time Complexity Steps
 Best: O(n log n) 1. Build max heap
 Average: O(n log n) 2. Swap root with last element
 Worst: O(n²) 3. Reduce heap size and heapify
4. Repeat
Stability
 Page 10 of 20 OKYRAJKUMAR

Time Complexity 9. Counting Sort

 Best: O(n log n) A non-comparison based sorting

 Average: O(n log n) algorithm used for integers.
 Worst: O(n log n)
Steps
Stability
1. Find the maximum value
❌ Unstable 2. Create a count array
3. Store frequency of each
element
4. Create prefix-sum array
8. Merge Sort 5. Place elements in output array

A perfect example of Divide and Time Complexity

Conquer.
O(n + k)
Steps (k = range of numbers)

1. Split array into two halves Stability

2. Sort each half recursively
3. Merge the two sorted halves ✔ Stable

Time Complexity

 Best: O(n log n) 10. Stable vs Unstable Sorting

 Average: O(n log n)
 Worst: O(n log n) Algorithm Stable
Stability Bubble Sort ✔

✔ Stable Insertion Sort ✔

Space Complexity Merge Sort ✔

O(n) extra space required Counting Sort ✔

Selection Sort ❌

Quick Sort ❌
 Page 11 of 20 OKYRAJKUMAR

Algorithm Stable

Heap Sort ❌ 12.2 Binary Search

Shell Sort ❌ Works only on sorted arrays.

Steps
Stable Sorting: preserves the relative
order of equal elements. 1. Find mid element
2. Compare key with mid
3. If smaller → left half
4. If larger → right half
11. Internal vs External Sorting 5. If equal → found

Type Details Examples Time Complexity

Bubble,  Best: O(1)

Internal All data is in  Worst: O(log n)
Quick,
Sorting main memory
Merge

Data stored
External External
on disk, too
Sorting Merge Sort
large for RAM

12. Searching Methods

12.1 Linear Search

Scans each element from beginning to

end.

Time Complexity

 Best: O(1)
 Worst: O(n)
 Page 12 of 20 OKYRAJKUMAR

UNIT – 4  Degree: Number of children of

a node
 Subtree: Tree formed by any
TREES node and its descendants

1. Tree Terminology 2. Binary Tree Terminology and

Properties
A Tree is a non-linear, hierarchical
data structure consisting of nodes A Binary Tree is a tree where each
connected by edges. node has at most two children:
Basic Terms  Left child
 Right child
 Node: Fundamental unit
containing data Binary Tree Properties
 Root: Topmost node of the tree
 Parent: Node which has one or 1. Maximum nodes at level i = 2ᶦ
more children 2. Maximum nodes in a tree of
 Child: Node directly connected height h = 2^(h+1) – 1
below a parent 3. Minimum height for n nodes =
 Siblings: Nodes with same
⌈log₂(n+1) – 1⌉
parent
4. For any binary tree:
 Leaf (External Node): Node
o n = e + 1
with no children
(n = nodes, e = edges)
 Internal Node: Node having at
least one child Types of Binary Trees
 Edge: Connection between two
nodes  Full Binary Tree: Every node
 Path: Sequence of nodes has 0 or 2 children
connected by edges  Complete Binary Tree: All
 Level: Distance from root (root levels completely filled except
is level 0 or 1 based on last, filled left to right
convention)  Perfect Binary Tree: All
 Depth of node: Length of path internal nodes have 2 children
from root to that node and all leaves at same level
 Height of node: Longest path  Skewed Binary Tree: All
from the node to its leaf nodes either to the left or right
 Height of tree: Height of the (like linked list)
root
 Page 13 of 20 OKYRAJKUMAR

Traversal Meaning

3. Tree Traversals  Inorder → Infix expression

 Preorder → Prefix expression
Traversal = visiting all nodes in a  Postorder → Postfix
specific order. expression

1. Inorder Traversal (L, Root, R) Example: Expression: (A + B) * C

Left → Root → Right Tree traversal results:

Output for BST gives sorted
sequence.  Inorder: A + B * C
 Preorder: * + A B C
2. Preorder Traversal (Root, L, R)  Postorder: A B + C *

Root → Left → Right

Used for copying tree.
5. Binary Search Tree (BST)
3. Postorder Traversal (L, R, Root)
A BST is a binary tree with special
Left → Right → Root ordering:
Used for deleting tree.
BST Property
4. Level Order Traversal
 Left subtree nodes < root
Visit nodes level by level (using  Right subtree nodes > root
queue).  No duplicates (in standard
BST)

4. Expression Trees
5.1 Operations on BST
Expression trees are binary trees used
to represent expressions. (a) Searching

Properties Steps:

 Leaves → operands (a, b, 5, x) 1. Compare key with root

 Internal nodes → operators (+, 2. If key < root → search left
-, *, /, ^) 3. If key > root → search right
4. If equal → found
 Page 14 of 20 OKYRAJKUMAR

Time Complexity 6. AVL Trees

 Best: O(log n) AVL Tree = Self-balancing BST

 Worst (skewed): O(n) Named after Adelson-Velsky &
Landis.

Balance Factor (BF)

(b) Insertion in BST
BF = height(left subtree) –
Steps: height(right subtree)

1. Compare key with root Valid AVL Tree Condition

2. Go left if key < root, else go
right  BF of every node must be –1,
3. Insert at the correct NULL 0, or +1
position
If BF goes outside this range →
rotations are required.

(c) Deletion in BST

Three cases: 6.1 Insertions in AVL Trees

Case 1: Node is a leaf After normal BST insert → Check

balance factor.
 Delete directly
There are 4 Imbalance Cases:
Case 2: Node has one child
1. LL Case (Left-Left)
 Replace node with its child
 Heavy on left subtree's left
Case 3: Node has two children  Fix: Right Rotation

 Find inorder successor 2. RR Case (Right-Right)

(minimum in right subtree)
 Replace node value with  Heavy on right subtree's right
successor  Fix: Left Rotation
 Delete successor node
3. LR Case (Left-Right)

 Left child heavy on right

 Fix:
 Page 15 of 20 OKYRAJKUMAR

o Left Rotation on child x

o Right Rotation on root \
y
4. RL Case (Right-Left) \
z
 Right child heavy on left
 Fix: Becomes:
o Right Rotation on child
o Left Rotation on root y
/ \
x z

6.2 Deletion in AVL Tree Left-Right Rotation (LR Fix)

1. Perform standard BST deletion 1. Left rotate child

2. Check balance factor from node 2. Right rotate root
to root
3. Apply the same rotations (LL, Right-Left Rotation (RL Fix)
RR, LR, RL)
4. Restore height and balance 1. Right rotate child
2. Left rotate root

6.3 Rotation Types

⭐ Summary
Right Rotation (RR Fix)
 Tree → non-linear, hierarchical
y  Binary tree → at most 2
/ children
x  Traversals → Inorder, Preorder,
/ Postorder, Level order
z  Expression trees → represent
expressions
Becomes:  BST → left < root < right
 AVL → height-balanced BST
x  Rotations → LL, RR, LR, RL
/ \
z y

Left Rotation (LL Fix)

 Page 16 of 20 OKYRAJKUMAR

UNIT – 5  Complete Graph: Every

vertex connected to every other

GRAPHS & HASHING

2. Representation of Graphs
1. Graphs – Basic Definitions and 1. Adjacency Matrix
Terminology
 2D matrix of size V × V
A Graph is a non-linear data  1 if edge exists, else 0
structure consisting of:  Space complexity: O(V²)
 Vertices (Nodes) 2. Adjacency List
 Edges (Connections between
vertices)  Each vertex stores a list of
connected vertices
Basic Terms  Space efficient for sparse
graphs
 Vertex (V): A node in the
 Space complexity: O(V + E)
graph
 Edge (E): A connection
between two vertices
 Adjacent vertices: Connected 3. Graph Traversal
by an edge
 Degree: Number of edges 3.1 Breadth First Search (BFS)
connected to a vertex
o In-degree (for directed BFS explores graph level by level
graph) using a queue.
o Out-degree
 Path: Sequence of vertices Algorithm
connected by edges
 Cycle: Path where first and last 1. Start from source vertex
vertex are same 2. Mark as visited
 Connected Graph: All 3. Push into queue
vertices can be reached 4. While queue not empty
 Directed Graph (Digraph): o Pop vertex
Edges have direction o Visit all unvisited
 Weighted Graph: Edges have neighbours
weights/costs
 Page 17 of 20 OKYRAJKUMAR

Applications

 Shortest path in unweighted 4.1 Prim’s Algorithm

graph
 Cycle detection Concept
 Level order traversal
Grows MST starting from one vertex,
always choosing minimum weight
edge connecting tree to a new vertex.
3.2 Depth First Search (DFS)
Time Complexity
DFS explores graph deep first using
stack/recursion.  Using adjacency matrix: O(V²)
 Using priority queue: O(E log
Algorithm V)

1. Start from source vertex

2. Mark as visited
3. Recursively visit all unvisited 4.2 Kruskal’s Algorithm
neighbours
Concept
Applications
Greedy method:
 Topological sort
 Detecting cycles 1. Sort all edges by weight
 Connected components 2. Pick smallest edge
3. Add it if it does not form a
cycle
4. Use Disjoint Set (Union-Find)
4. Minimum Spanning Tree (MST) for cycle detection

MST is a subset of edges that: Time Complexity

 Connects all vertices O(E log E)

 Has minimum total weight
 No cycles
 Page 18 of 20 OKYRAJKUMAR

7. Collision Resolution Techniques

5. Single Source Shortest Path 7.1 Open Hashing (Separate

Chaining)
Dijkstra’s Algorithm
Each hash table index stores a linked
Finds shortest path from a source to list of keys.
all vertices in a weighted graph
(non-negative weights). Features

Steps  Simple implementation

 Unlimited keys per index
1. Initialize distances as infinity  Space for pointers needed
2. Distance[source] = 0
3. Choose vertex with minimum Time Complexity
distance (priority queue)
4. Relax all adjacent edges Average: O(1)
5. Repeat until all nodes Worst: O(n)
processed

Time Complexity
7.2 Closed Hashing (Open
 With min-heap: O(E log V) Addressing)

All elements stored directly in the

hash table.
6. Hashing
If collision occurs → search next free
Hashing is a technique to map large index.
keys into small values using a hash
function.

Hash Function Types of Open Addressing

hash(key) = index 1. Linear Probing

Problems Check next index:

(h(key) + i) % table_size
 Different keys may generate
same hash → Collision Problem

Primary clustering
 Page 19 of 20 OKYRAJKUMAR

8. Rehashing

2. Quadratic Probing When load factor (α) is too high, hash

table becomes full.
Probe sequence:
h(key) + i² Steps

Pros 1. Create a larger hash table

(usually double size)
Reduces clustering 2. Reinsert all elements using new
hash function
Cons
Purpose
May fail to find empty slot if table
size not prime  Reduce collisions
 Maintain constant time
performance

3. Double Hashing

Uses second hash function: 9. Recent Trends in Data Structures

(h1(key) + i * h2(key)) % & Algorithms
table_size
1. Self-Balancing Trees
Advantages
 Red-Black Trees
 Best collision resolution  Splay Trees
 Minimum clustering  B-Trees, B+ Trees (used in
databases)

2. Advanced Hashing
4. Random Probing
 Cuckoo Hashing
Random number generator used to  Perfect Hashing
decide next index.  Hopscotch Hashing

3. Graph Algorithms

 Floyd–Warshall (All-pairs
shortest path)
 A* Search Algorithm
 Page 20 of 20 OKYRAJKUMAR

 Johnson’s algorithm  Open Addressing → linear,

quadratic, double hashing
4. Data Structures for Big Data  Rehashing → resize table

 Bloom Filters
 Skip Lists
 Trie (Prefix Trees) ⭐ FOR ANY ENQUIRY
5. Machine Learning Oriented
Algorithms 📞 Mobile:

 Gradient-based optimization +91 77338 02779

(GD, SGD)
 Graph Neural Networks 📧 Email:

okyrajkumarbusiness@[Link]

✨ Feel free to contact for any

⭐ Exam-Oriented Summary
queries, support, or additional
Graph information.

 Represented using adjacency We are always available to assist you

matrix/list and provide the best guidance
 Traversal: BFS (queue), DFS possible.
(stack)

MST

 Prim → start from one node

OKYRAJKUMAR
 Kruskal → sort edges + union-
find

Shortest Path

 Dijkstra → non-negative
weights

Hashing

 Separate Chaining → linked list