Tab 1

Algorithm – Definition and Exampl

[Link]
v=itbkP50iggM&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=2

● Definition:
An algorithm is a finite set of steps or instructions to solve a particular problem.
Each step should take finite time to execute.

Example:

Problem: Sum of two numbers

Step 1: Read A
Step 2: Read B
Step 3: Sum = A + B
Step 4: Print Sum

● This is the algorithm for adding two numbers before converting it into a program (like in
C, Java, or Python).

Characteristics of a Good Algorithm

1. Finiteness:

○ Must have a finite number of steps.

○ Each instruction must take finite time.

○ Infinite loops (like while(1)) are not allowed.

2. Unambiguity:

○ Instructions must be clear and unambiguous.

○ Avoid confusing or incorrect symbols (e.g., using the wrong operator).

Analysis of Algorithms
 ● Meaning:
Comparing multiple algorithms (like linear vs binary search, quick sort vs merge sort)
to see which one performs better.

● Parameters Used for Comparison:

○ Time (execution speed)

○ Space (memory usage)

○ Others: registers, bandwidth, etc.

(Time and space are most common.)

Types of Analysis
1. Priori (Before Execution):

○ Based on counting iterations or steps, not actual time.

○ Independent of hardware.

○ Gives an approximate result.

○ Example: Counting how many times each line runs in an algorithm.

2. Posterior (After Execution):

○ Based on actual running time after executing code.

○ Dependent on hardware (CPU, system speed).

○ Gives an exact result, but varies across machines.

Why Priori Analysis is Preferred

● It gives uniform results (not affected by hardware).

● Helps estimate worst-case, best-case, and average-case performance.

Asymptotic Notations (for Analysis)

 ● Used to represent algorithm efficiency:

○ Big O (O) – Worst case

○ Omega (Ω) – Best case

○ Theta (Θ) – Average case

○ Small o, small omega – Other comparative notations

Asymptotic Notations – Overview

[Link]
v=7dz8Iaf_weM&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=3

Definition:
Asymptotic notation is the mathematical way to represent time complexity of an algorithm.
It helps compare algorithms without executing them (prior analysis).
It shows how running time grows with input size (n).

● Purpose:
To analyze and compare algorithms efficiently using a standard mathematical form.

Main Asymptotic Notations

1. Big O (O): Upper Bound / Worst Case
 ○ Represents maximum time an algorithm can take.

○ Shows the upper limit of growth rate (at most time).

○ Mathematically:
f(n) ≤ c·g(n) for n ≥ k
(c and k are positive constants)

○ Example:
f(n) = 2n² + n
→ Dominant term = n²
→ f(n) = O(n²)
(Choose c = 3, n ≥ 1 to satisfy condition)

○ Meaning: Algorithm takes at most proportional to n² time.

2. Big Omega (Ω): Lower Bound / Best Case

○ Represents minimum time an algorithm will take.

○ Shows the lower limit of growth rate (at least time).

○ Mathematically:
f(n) ≥ c·g(n) for n ≥ k

○ Example:
f(n) = 2n² + n
→ f(n) = Ω(n²)
(Choose c = 2, n ≥ 0)

○ Meaning: Algorithm takes at least proportional to n² time.

3. Theta (Θ): Tight Bound / Average Case

○ Represents average growth rate.

○ Combines upper and lower bounds.

○ Mathematically:
c₁·g(n) ≤ f(n) ≤ c₂·g(n) for n ≥ k

○ Example:
f(n) = 2n² + n
→ f(n) = Θ(n²)
 (2n² ≤ f(n) ≤ 3n²)

○ Meaning: Algorithm grows exactly proportional to n².

In the expression f(n) ≤ c·g(n) for n ≥ k,

the k simply represents a threshold value of input size (n) beyond which the comparison
between f(n) and g(n) always holds true.

Let’s break it down:

● f(n): the actual time function of your algorithm.

● g(n): a simpler function (like n, n², log n) used to compare growth.

● c: a constant multiplier to adjust the scale.

● k: the point (or smallest input size) after which the inequality stays true for all larger n.

Example
Say you have:
f(n) = 2n² + n
and you claim f(n) = O(n²)

To prove it, you must find c and k such that

2n² + n ≤ c·n² for all n ≥ k

Let’s test:
If c = 3, then
2n² + n ≤ 3n²
→ n ≤ n² → true for n ≥ 1

✅ So here c = 3 and k = 1

Simple Analogy
● Think of searching a topic in a book (linear search):

○ Best Case (Ω): Found on first page

○ Worst Case (O): Found on last page

○ Average Case (Θ): Found around the middle

Other Notations
4. Little o:

○ Similar to Big O but strictly less than (no equality).

○ f(n) < c·g(n)

5. Little omega (ω):

○ Similar to Big Omega but strictly greater than (no equality).

○ f(n) > c·g(n)

1. Recap of Notations
Notation Meaning Relation Simple Form

Big O (O) Upper bound / worst case f(n) ≤ c·g(n) a≤b

Big Omega (Ω) Lower bound / best case f(n) ≥ c·g(n) a≥b

Theta (Θ) Tight bound / average case c₁·g(n) ≤ f(n) ≤ a=b

c₂·g(n)
Little o (o) Strictly less than (no equality) f(n) < c·g(n) a<b

Little omega (ω) Strictly greater than (no equality) f(n) > c·g(n) a>b

Example:
If f(n) = 2n²
→ Tightest upper and lower bound = n²
→ f(n) = Θ(n²), O(n²), Ω(n²)

2. Properties of Asymptotic Notations

[Link]
v=OLttwv_4Ltw&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=4

a) Reflexive Property
● Definition: a relation that holds when f(n) compared with itself is true.
(f(n) = O(f(n)), etc.)

Notation Holds Reason

?
Big O (O) ✅ Yes Has ≤ sign

Big Omega (Ω) ✅ Yes Has ≥ sign

Theta (Θ) ✅ Yes Has = sign

Little o (o) ❌ No f(n) < f(n) is false

Little omega (ω) ❌ No f(n) > f(n) is false

b) Symmetric Property
● Definition: if f(n) = g(n) then g(n) = f(n).
Only works with equality-based relations.

Notation Holds Reason

?
 Theta (Θ) ✅ Yes Equality both sides

Big O (O) ❌ No a ≤ b doesn’t mean

b≤a
Big Omega (Ω) ❌ No a ≥ b doesn’t mean
b≥a
Little o (o) ❌ No a < b not reversible

Little omega (ω) ❌ No a > b not reversible

c) Transitive Property
● Definition: if f(n) R g(n) and g(n) R h(n) → f(n) R h(n)

Notation Holds Example

?
Big O (O) ✅ Yes if f ≤ g and g ≤ h → f
≤h
Big Omega (Ω) ✅ Yes if f ≥ g and g ≥ h → f
≥h
Theta (Θ) ✅ Yes if f = g and g = h → f
=h
Little o (o) ✅ Yes if f < g and g < h → f
<h
Little omega (ω) ✅ Yes if f > g and g > h → f
>h

3. Quick Example
If f(n) = n²
Then:

● O(n³) → upper bound (larger function)

● Ω(n) → lower bound (smaller function)

● Θ(n²) → tight bound

● o(n³) → strictly smaller

● ω(n) → strictly larger

Asymptotic PDF2

Why Asymptotic Analysis (in simple words)

● Machine-independent:
It helps us compare algorithms without worrying about the computer’s speed or
hardware differences.

● No need to run the program:

We can analyze how an algorithm performs mathematically without actually
implementing it.

● Describes growth:
It shows how the time or space used by an algorithm increases as the input size (n)
gets larger.

● Standard comparison:
Using notations like Big O, Big Omega, and Big Theta, we can describe:

○ Worst case → Big O

○ Best case → Big Omega

○ Average case → Big Theta

● Main goal:
To understand how performance changes as input size grows — in other words,
how scalable the algorithm is.

Theta (Θ) Notation – Simple Explanation

● Meaning:
If f(n) = Θ(g(n)), it means f(n) grows at the same rate as g(n) for large values of n.
So, f(n) is always between c₁·g(n) and c₂·g(n) for n ≥ n₀, where c₁ and c₂ are positive
constants.

● In simple words:
Θ gives both upper and lower bounds — it tells us the exact rate of growth of an
algorithm’s running time.

● Rule of thumb:
To find Θ, ignore small terms and constants, because for large n, they don’t affect
growth much.

● Example:
f(n) = 3n³ + 6n² + 6000
→ Θ(n³)
(Here, n³ dominates as n becomes large; the other terms become negligible.)
Theta (Θ) Notation – In Simple Words
● Definition:
f(n) = Θ(g(n)) means f(n) is both O(g(n)) (upper bound) and Ω(g(n)) (lower bound).

● Meaning:
Θ gives a tight bound — it shows the exact growth rate of an algorithm.
The running time grows neither faster nor slower than g(n).

● Example:
3n² + 5n + 2 = Θ(n²)
→ For large n, the n² term dominates, so the algorithm grows like n².

Transpose symmetry

[Link]

Rules for Combining Functions

1. Addition

● When adding two functions:

f(n) + g(n) grows as fast as the bigger one among them.
So,

○ O(max(f(n), g(n))) → upper bound

○ Θ(max(f(n), g(n))) → exact (tight) bound

Example:
If f(n) = n² and g(n) = n,
→ f(n) + g(n) = Θ(n²)
(because n² dominates n)
2. Multiplication

● When multiplying two functions:

The result grows as their product.
So,

○ O(f(n) * g(n)), Ω(f(n) * g(n)), Θ(f(n) * g(n))

Example:
If f(n) = n² and g(n) = n,
→ f(n) * g(n) = Θ(n³)

In short:

● Addition: growth ≈ bigger term

● Multiplication: growth ≈ product of terms

Here’s the simple idea:

Addition
When you add two functions, the bigger one dominates.

● f(n) + g(n) grows like the larger of the two.

○ O(max(f(n), g(n))) → upper bound

○ Θ(max(f(n), g(n))) → exact growth

Example:
If f(n)=n² and g(n)=n, then f(n)+g(n)=Θ(n²).

Multiplication
When you multiply two functions, their growth rates multiply.

● f(n) × g(n) = O(f(n) × g(n)) = Θ(f(n) × g(n))

Example:
If f(n)=n² and g(n)=n, then f(n)×g(n)=Θ(n³).

Transitivity Property (Big O Notation)

If
f(n) = O(g(n)) and g(n) = O(h(n)),
then
👉 f(n) = O(h(n))

Meaning:
If one function grows no faster than a second, and the second grows no faster than a third,
then the first also grows no faster than the third.

Example:
If

● f(n) = n

● g(n) = n²

● h(n) = n³

Then:
n = O(n²) and n² = O(n³)
➡ so n = O(n³)

1. Transpose Symmetry
● Rule:
f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

● Meaning:
If one function (f(n)) grows no faster than another (g(n)),
then g(n) grows at least as fast as f(n).
They describe the same relationship from opposite sides.

● Example:
If f(n) = n and g(n) = n²
→ n = O(n²)
→ n² = Ω(n)

2. Theta (Θ) Notation Definition

● Rule:
f(n) = Θ(g(n)) if there exist constants c₁, c₂, and n₀ such that:
 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀

● Meaning:
Θ shows that f(n) grows at the same rate as g(n) —
not slower and not faster.

● In simple terms:
For large inputs:

○ f(n) never goes below c₁·g(n)

○ f(n) never goes above c₂·g(n)

→ Both grow in the same order.

● Example:
3n² + 5n + 2 = Θ(n²)
(n² dominates; both grow similarly for large n)

Example – Theta Notation

Let:
f(n) = 5n + 3
g(n) = n

● For large n, the constant (3) becomes negligible, so f(n) behaves like 5n.

● Choose constants c₁ = 4, c₂ = 6, and n₀ = 10.

● For n ≥ 10:
4n ≤ 5n + 3 ≤ 6n
✅ This satisfies the Theta condition.

So, f(n) = Θ(n).

TIME SPACE COMPLEXITY:

[Link]
v=19N3gWGBh5E&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=5

🧠 Comparison of Time Complexities (From Fastest →

Slowest)
Order Time Complexity Example / Remarks
1. O(1) Constant Time Hashing, accessing array element, finding median in
sorted array. Fixed number = constant = O(1).

2. O(log Double Very fast, smaller than log n.

log n) Logarithmic Time

3. O(log Logarithmic Time Binary Search, Divide & Conquer type problems.
n)

4. O(√n) Root n Time Comes between log n and linear (n).

5. O(n) Linear Time Linear Search, Best case of Insertion Sort.

6. O(n log Linearithmic Time Merge Sort, Quick Sort (average case), Heap Sort.
n)

7. O(n²) Quadratic Time Bubble Sort, Insertion Sort (worst case), Selection Sort.

8. O(n³) Cubic Time Matrix Multiplication (simple).

9. O(nᵏ) Polynomial Higher-degree polynomial algorithms.

Time (k ≥ 4)

10. O(2ⁿ) Exponential Time Subset Sum, Travelling Salesman (Brute Force), many
DP problems before optimization.

11. O(nⁿ) Factorial Time Permutation-based or brute-force solutions.

12. O(2²ⁿ) Double Extremely slow; theoretical or recursive problems.

Exponential Time

📊 Growth Comparison (increasing order)

O(1) < O(log log n) < O(log n) < O(√n) < O(n)
< O(n log n) < O(n²) < O(n³) < O(nᵏ)

< O(2ⁿ) < O(nⁿ) < O(2²ⁿ)

💬 Key Points to Remember

● "Order" = Upper bound / maximum time (Big O Notation).
→ Represents worst-case growth rate.

● Constant values (like 10³ or 10⁹) are all O(1) in algorithms.

→ Because the number is fixed.

● Always test with large n values (not small ones)

→ Differences between complexities become clearer for big inputs.

● Sorting algorithms:

○ Merge Sort → O(n log n)

○ Quick Sort → Average O(n log n), Worst O(n²)

○ Bubble / Insertion / Selection → O(n²)

⚡ Simple Graph Trend (Time ↑ vs Input ↑)

Constant ──> Log Log n ─> Log n ─> √n ─> n ─> n log n ─> n² ─> n³ ─> 2ⁿ ─> nⁿ
─> 2²ⁿ

↑ ↑ ↑

Fastest Medium Slowest (Exponential)

L-1.6: Time Complexities of all Searching and Sorting Algorithms in 10

minute | GATE & other Exams

⚡ Searching Algorithms
 Algorithm Best Average Worst Notes
Case Case Case

Binary Search O(1) O(log n) O(log n) Works only on sorted data

(divides list into halves)

Sequential / Linear O(1) O(n/2) ≈ O(n) Works on unsorted data

Search O(n)

🔹 Sorting Algorithms
Algorithm Best Average Worst Notes
Case Case Case

Quick Sort O(n log O(n log n) O(n²) Worst when data already sorted & first
n) element is pivot

Merge Sort O(n log O(n log n) O(n log Same for all cases
n) n)

Insertion Sort O(n) O(n²) O(n²) Best when data already sorted

Bubble Sort O(n) O(n²) O(n²) Simple but slow

Selection O(n²) O(n²) O(n²) Always quadratic

Sort

Heap Sort O(n log O(n log n) O(n log Based on heap (max/min)
n) n)

Huffman O(n log O(n log n) O(n log Used in compression

Coding n) n)

🌳 Heap Operations
 Operation Single For N Notes
Element Elements

Insertion in Heap O(log n) O(n log n) Re-heapify after each

insert

Deletion in Heap O(log n) O(n log n) Rearrange after

removing root

Height of Complete Binary — O(log n) n = no. of elements

Tree (CBT)

🌐 Graph Algorithms
Algorithm Time Notes
Complexity

Prim’s (Adj. Matrix) O(n²) Shortest spanning tree

Prim’s (Using Heap) O((V + E) log V) Optimized version

Kruskal’s O(E log E) Uses edge sorting

DFS / BFS O(V + E) V = vertices, E = edges

Floyd-Warshall (All-Pair Shortest O(n³) For all pairs

Path)

Dijkstra (Single-Source Shortest O(V²) Using matrix; can improve with

Path) heap

🧾 Quick Summary Table

 Category Common Complexities

Searching O(1), O(log n), O(n)

Sorting O(n), O(n log n), O(n²)

Graph / Heap O(V + E), O(n log n), O(n³)

💡 Tips for Exams

● Mostly Big-O (upper bound) is asked.

● Binary Search → O(log n)

● Merge / Heap / Quick (avg) → O(n log n)

● Bubble / Insertion / Selection (worst) → O(n²)

● Graphs (DFS/BFS) → O(V + E)

● Floyd-Warshall → O(n³)

L-1.7: Question#1 on Comparison of Various Time Complexities | GATE Questions

Ans is “b”

🎯 Goal:

To find which function grows faster (is bigger) as n increases.

🧩 Given Example
● F₁(n) = n² log n

● F₂(n) = (n log n)¹⁰

We need to find which one grows faster.

⚙️Method 1: Substitution (Put Values)

1. Try with small n (like 16) → might mislead.

2. Always check with large n (e.g., 10⁹) → gives true dominance.

3. For large n, powers (like (log n)¹⁰) grow slower than n terms.
⇒ n² log n grows faster.

✅ Therefore, F₁(n) > F₂(n) for large n.

🧮 Method 2: Simplify Algebraically

F₁(n) = n² log n
F₂(n) = (n log n)¹⁰ = n¹⁰ (log n)¹⁰

Divide F₂ by F₁:
→ (n¹⁰ (log n)¹⁰) / (n² log n) = n⁸ (log n)⁹

As n → ∞, this grows huge.

So, F₂(n) grows faster → actually dominates.

✅ Final comparison:
F₁(n) = O(F₂(n))
or
F₂(n) = Ω(F₁(n))
🧠 Question: Compare the following time complexities
Given functions:

● F₁(n) = 2ⁿ

● F₂(n) = n^(3/2)

● F₃(n) = n log n

● F₄(n) = n^(log n)

We have to arrange them in increasing order of growth.

🔹 Step 1 – Recall Basic Order of Growth

General order:

log n < √n < n < n log n < n² < n³ < ... < 2ⁿ < nⁿ

So here, 2ⁿ (exponential) will be the largest term.

🔹 Step 2 – Substitute a value (to check)

Take n = 16 (2⁴), easier for log base 2.

Functio Substitution Result (approx)

n

F₁(n) 2¹⁶ 65,536

F₂(n) 16^(3/2) 64

F₃(n) 16 × log₂16 = 16 × 64
4

F₄(n) 16^(log₂16) = 16⁴ 65,536

So:
F₃ ≈ F₂ < F₄ < F₁

🔹 Step 3 – Verify with larger n (n = 256 = 2⁸)

Functio Simplified form Observation

n

F₁(n) 2²⁵⁶ Very large (exponential)

F₂(n) 256^(3/2) = 2¹² 4096

F₃(n) 256 × 8 = 2048 Smaller

F₄(n) 256⁸ = (2⁸)⁸ = Huge (next to exponential)

2⁶⁴

Order confirmed.

✅ Final Increasing Order of Growth

F3(n)<F2(n)<F4(n)<F1(n)F₃(n) < F₂(n) < F₄(n) < F₁(n)F3(n)<F2(n)<F4(n)<F1(n)
or equivalently:

nlog⁡n<n3/2<nlog⁡n<2nn \log n < n^{3/2} < n^{\log n} < 2^nnlogn<n3/2<nlogn<2n

💡 Quick Tip
● Use large n values to check dominance.

● For simplification:

○ n3/2=nnn^{3/2} = n \sqrt{n}n3/2=nn

○ nlog⁡nn^{\log n}nlogn grows faster than any polynomial but slower than 2n2^n2n.

● Exponential > Power (Polynomial) > Logarithmic.

Final Answer:
✅ Increasing Order → F₃, F₂, F₄, F₁

L-3.0: Divide and Conquer | Algorithm

L-3.1: How Quick Sort Works | Performance of Quick Sort with Example | Divide and Conquer
🎯 Quick Sort – Gate Smashers Notes
1 What is Quick Sort?
1️⃣

● Quick Sort is a Divide and Conquer sorting algorithm.

● Works by partitioning the array around a pivot element.

2️⃣What is Divide and Conquer?

● Divide big problem (size N) → smaller sub-problems (e.g. N/2, N/2).

● Solve all sub-problems.

● Conquer → combine all results for the final answer.

● Quick Sort follows this approach.

3️⃣How Quick Sort Divides (Partition Concept)

● Select a pivot element (often the first element).

● Use two pointers:

○ P → moves from left to right (RHS), stops when it finds element greater than
pivot.

○ Q → moves from right to left (LHS), stops when it finds element smaller than
pivot.

● Swap elements at P and Q until they cross.

● When P and Q cross, swap pivot with the element at Q.

● After one pass → pivot reaches its correct sorted position.

4 Why Use +∞ and Not −∞?

4️⃣
 ● +∞ is placed at end to ensure P stops when no greater element is found.

● No need for −∞ because Q checks “≤ pivot”, so it naturally stops at pivot.

5️⃣When to Swap?

Condition Action

P and Q have NOT crossed Swap elements at P and Q

P and Q have crossed or are Swap pivot with element at

equal Q

6️⃣What Happens After First Pass?

● Pivot reaches correct sorted position.

● Array divides into two parts:

○ Left side → elements smaller than pivot

○ Right side → elements greater than pivot

● Apply Quick Sort recursively on both sides.

7️⃣Example Flow

Example Array: 35, 5, 4, 3, 2, 1, +∞

→ Pivot = 35
→ P and Q move, swap elements accordingly
→ After 1st pass, pivot 35 in correct position.
→ Divide → Apply same logic to left & right parts recursively.

8️⃣When Pivot is in Middle (Best/Average Case)

 ● Problem divides evenly → N/2 and N/2 – 1.

● Recurrence relation:
T(N) = 2T(N/2) + N
(N for scanning whole array each pass)

● Using Master Method/Substitution,

Time Complexity = O(N log N) (average case).

9️⃣Key Questions Asked in Exams

1. Concept of Divide and Conquer in Quick Sort.

2. What is Pivot and why is it important?

3. What is the role of pointers P and Q?

4. Why add +∞ and not −∞?

5. When do we swap pivot with Q?

6. What happens after one pass?

7. Derive Recurrence Relation for average case.

8. Find Average Case Time Complexity.

🧠 Summary
● Technique: Divide and Conquer

● Key step: Partitioning using pivot

● Recurrence: T(N) = 2T(N/2) + N

● Average Case: O(N log N)

● Pivot choice decides performance

Quick Sort – Performance Analysis

L-3.2: Performance of Quick Sort | Worst Case Time Complexity with Example | Algorithm

1. What Affects Performance

● The performance of Quick Sort depends on where the pivot element is placed after
each partition.

● The position of the pivot determines whether the partition is balanced or unbalanced.

2. Best Case
● When: Pivot divides the array equally into two parts (N/2 and N/2).

● Time Complexity: O(N log N)

● Reason: Each partition is balanced, and the array reduces in size efficiently.

3. Average Case
● Usually close to the best case.

● Time Complexity: O(N log N)

4. Worst Case
● When: Pivot always becomes the smallest or largest element,
so one side has N−1 elements and the other has 0 elements.

● Happens when the array is already sorted (ascending or descending).

Recurrence Relation:
T(N) = T(N−1) + N

Time Complexity:
O(N²)

5. Example (Worst Case)

Array: [10, 20, 30, 40, 50, 60, 70]

● Pivot = 10 → left side = 0 elements, right side = N−1 elements

● Next pivot = 20 → left side = 0, right side = N−2

● Continues until all elements are sorted individually

→ Results in unbalanced partitions → O(N²)

6. Summary
Case Pivot Position Time Complexity

Best Middle (Balanced) O(N log N)

Average Random (Moderately O(N log N)

Balanced)
Worst Extreme (Sorted Array) O(N²)

Merge Sort – Working and Concept

L-3.3: How Merge Sort Works?? Full explanation with example

1. Definition
● Merge Sort is a Divide and Conquer algorithm.

● It repeatedly divides the array into smaller parts, sorts them, and merges them back in
sorted order.

2. Key Idea
● Divide: Split the array into two halves until each sub-array has only one element.

● Conquer (Merge): Combine (merge) the sub-arrays while sorting them in ascending
order.

3. Steps (Example)
Given array:
[6, 4, 2, 1, 9, 8, 3, 5]

1. Divide Phase:

○ Split into halves → [6,4,2,1] and [9,8,3,5]

○ Keep dividing until single elements remain:

[6] [4] [2] [1] [9] [8] [3] [5]

2. Conquer (Merge) Phase:

○ Start merging pairs while sorting:

[6] [4] → [4,6]
[2] [1] → [1,2]
[9] [8] → [8,9]
[3] [5] → [3,5]

3. Merge again:
[4,6] + [1,2] → [1,2,4,6]
[8,9] + [3,5] → [3,5,8,9]

4. Final Merge:
[1,2,4,6] + [3,5,8,9] → [1,2,3,4,5,6,8,9] ✅ (Sorted array)

4. How Merging Works

● Use two pointers:

○ i for left array (L), j for right array (R).

● Compare L[i] and R[j]:

○ Write the smaller one first, move that pointer forward.

● Continue until all elements are merged.

5. Time Complexity
● Best Case: O(n log n)
 ● Average Case: O(n log n)

● Worst Case: O(n log n)

(Same in all cases)

6. Space Complexity
● Requires extra space for temporary arrays during merging.
→ O(n)

7. Summary
Phase Description Example

Divide Split array until one element [6,4,2,1,9,8,3,5] → [6] [4]

remains [2] [1] ...
Conquer Combine while sorting [6] + [4] → [4,6]
(Merge)

Time O(n log n) Always same for all cases

Complexity

Space O(n) Needs extra space for merging

Complexity
L-3.5: Imp. Question on Merge Sort | Divide and Conquer | Algorithm

Bubble Sort – Working and Key Points

L-3.6: How Bubble Sort Works | Performance of Bubble Sort | All Imp Points with
Example | Algorithm

1. Definition
● Bubble Sort is a simple comparison-based sorting algorithm.

● It repeatedly compares adjacent elements and swaps them if they’re in the wrong
order.

2. How It Works
● Start from the first element and compare it with the next one.

● If the next element is smaller, swap them.

● Continue comparing until the end of the array — this completes one pass.

● After each pass, the largest element moves to its correct position (end of the array).

● Repeat for the remaining unsorted part.

3. Example

Unsorted array: [10, 9, 11, 6, 15, 2]

Pass 1:
→ Compare & swap where needed → [9, 10, 6, 11, 2, 15]
(Largest element 15 moved to correct position)

Pass 2:
→ [9, 6, 10, 2, 11, 15]
(Next largest element 11 fixed)

Pass 3:
→ [6, 9, 2, 10, 11, 15]
(Third largest element 10 fixed)

And so on — each pass places the next largest element correctly.

4. Key Observation
After every pass:
✅ One more element is sorted (placed correctly at the end).
✅ Remaining comparisons reduce:

● 1st pass → (n−1) comparisons

● 2nd pass → (n−2)

● 3rd pass → (n−3)

… up to 1

5. Time Complexity
● Total comparisons: (n−1) + (n−2) + (n−3) + … + 1
= n(n−1)/2 = O(n²)

● So, Worst case = O(n²)

● Best case (already sorted) = O(n) (if optimized with a flag)

6. Important Points
● After each pass, the largest element reaches its correct position.

● Number of swaps and comparisons are maximum in the worst case (reverse-sorted
array).

● Common exam questions:

1. Array status after 2 or 3 passes

2. Total number of swaps

3. Time complexity (best, average, worst)

7. Summary Table
Case Description Time Complexity

Best Already sorted O(n)

Averag Random order O(n²)

e
Worst Reverse order O(n²)

Insertion Sort – Working and Key Points

L-3.7: Insertion Sort | Time Complexity Analysis | Stable Sort | Inplace Sorting

🎯 Introduction
● Insertion Sort is a simple and intuitive sorting algorithm.

● Works similarly to the way we arrange cards in our hands while playing.

🃏 Real-Life Analogy (Card Example)

● Imagine you are arranging playing cards in order:
 ○ Pick the first card → keep it aside (no comparison needed).

○ Pick the next card → place it in the correct position relative to the first.

○ For every new card, compare it with the sorted cards (on the left) and insert it
into its correct position.

● The same idea applies in Insertion Sort.

⚙️How Insertion Sort Works

Example Array:

[40, 20, 60, 10, 50, 30]

Step-by-step:

1. Start with the first element → [40] (already sorted)

2. Take next element 20 → compare with 40, since 20 < 40, insert before → [20,
40]

3. Take next element 60 → compare with 40, since 60 > 40, place after → [20, 40,
60]

4. Take next element 10 → compare with 60, 40, 20, insert before all → [10, 20,
40, 60]

5. Take next element 50 → compare with 60, insert before 60 → [10, 20, 40, 50,
60]

6. Take last element 30 → compare with 60, 50, 40, insert before 40 → [10, 20,
30, 40, 50, 60]

✅ Final Sorted Array: [10, 20, 30, 40, 50, 60]

💻 Algorithm / Pseudocode
for j = 2 to length(A)
key = A[j]
 i = j - 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key

Explanation:

● key stores the current element to be placed correctly.

● i moves backward through the sorted section.

● Elements greater than key are shifted one position right.

● When correct spot is found, key is placed there.

🕒 Time Complexity Analysis

Case Order of Order of Overall Time
Comparison Swapping Complexity

Best Case (Ascending N - 1 comparisons 0 swaps O(N)

Order)

Worst Case (Descending N(N-1)/2 N(N-1)/2 swaps O(N²)

Order) comparisons

Average Case — — O(N²)

Explanation:
● Best Case: Elements already sorted → only one comparison each time → O(N)

● Worst Case: Elements in reverse order → each new element compared with all
previous → O(N²)

● Average Case: Roughly half comparisons per element → still O(N²)

🔁 Space Complexity
● Uses only a temporary variable (key) → constant extra space.

● Space Complexity = O(1)

● Therefore, it is an In-place Sorting Algorithm.

⚖️Stability
● Stable Sorting Algorithm

● It maintains the relative order of elements with equal keys.

○ Example: [5A, 2, 3, 5B, 1] → Sorted: [1, 2, 3, 5A, 5B]

○ The order of 5A and 5B remains same.

🌐 Online Algorithm
● Called Online Algorithm because:

○ It can sort elements as they arrive.

○ Doesn’t wait for the full input before starting.

○ Example: After each new element, it adjusts the array immediately.

📋 Key Points Summary

Property Description

Type Comparison-based sorting

Approach Incremental / iterative

In-place? Yes

Stable? Yes
 Best Case Time O(N)

Worst Case Time O(N²)

Average Case O(N²)

Time
Space Complexity O(1)

Sorting Nature Online sorting algorithm

Practical Use Works efficiently for small datasets or nearly sorted

data

🧩 Advantages
● Simple and easy to implement.

● Performs well on small datasets.

● Efficient for partially sorted arrays.

⚠️Disadvantages
● Inefficient for large datasets (O(N²)).

● High number of comparisons and shifts in worst case.

🧠 Selection Sort – Complete Notes

L-3.8: Selection Sort | Time Complexity(Best, Avg & Worst) Analysis | Stable or Not | Inplace or
Not

🎯 Introduction
● Selection Sort is a simple comparison-based sorting algorithm.

● It is important for competitive exams, college, and university exams, and often asked
in interviews.
 ● The algorithm repeatedly selects the minimum element from the unsorted portion and
places it in the correct position of the sorted portion.

⚙️Concept
● The main idea:
In each pass, find the minimum element from the unsorted array and swap it with the
first unsorted element.

🧩 Working Principle (Step-by-Step Example)

Let’s take an example array:
[40, 20, 60, 10, 50, 30]

🔹 Step 1 (First Pass)

● Assume first element (40) is minimum → min = 40

● Compare 40 with all others:

○ 20 < 40 → min = 20

○ 60 > 20 → no change

○ 10 < 20 → min = 10

○ 50 > 10 → no change

○ 30 > 10 → no change

● Minimum element found = 10

● Swap 10 and 40
→ Array becomes [10, 20, 60, 40, 50, 30]

✅ After Pass 1: Minimum element (10) is placed at first position.

🔹 Step 2 (Second Pass)

 ● Now start from index 2 (element 20)

● Assume min = 20

● Compare 20 with rest:

○ 60 > 20

○ 40 > 20

○ 50 > 20

○ 30 > 20

● No smaller element found → No swap needed

✅ After Pass 2: [10, 20, 60, 40, 50, 30]

🔹 Step 3 (Third Pass)

● Start from index 3 (element 60)

● Assume min = 60

● Compare with others:

○ 40 < 60 → min = 40

○ 50 > 40

○ 30 < 40 → min = 30

● Minimum element = 30

● Swap 30 and 60
→ [10, 20, 30, 40, 50, 60]

✅ After Pass 3: First three elements are sorted.

🔹 Step 4 & 5
● The process continues:
 ○ 4th pass: 40 already at right place

○ 5th pass: 50 already at right place

● After final pass, array is fully sorted.

✅ Final Sorted Array: [10, 20, 30, 40, 50, 60]

💻 Pseudocode / Algorithm
for i = 0 to n - 2
min_index = i
for j = i + 1 to n - 1
if A[j] < A[min_index]
min_index = j
swap(A[i], A[min_index])

🧮 Time Complexity Analysis

🔹 Number of Comparisons
● In each pass, comparisons are made with remaining elements:

○ (n-1) + (n-2) + (n-3) + ... + 1

= n(n-1)/2
= O(n²) comparisons

🔹 Number of Swaps
● Only one swap per pass, even in the worst case.

● Total = O(n) swaps

🔹 Best Case (Array already sorted)

 ● Example: [10, 20, 30, 40, 50, 60]

● Comparisons = n(n-1)/2 → O(n²)

● Swaps = 0 → O(1)

● Best Case Time Complexity: O(n²)

🔹 Worst Case (Array in descending order)

● Example: [60, 50, 40, 30, 20, 10]

● Comparisons = n(n-1)/2 → O(n²)

● Swaps = n → O(n)

● Worst Case Time Complexity: O(n²)

🔹 Average Case
● Comparisons ≈ n(n-1)/2 → O(n²)

● Swaps ≈ n → O(n)

● Average Case Time Complexity: O(n²)

🧠 Space Complexity
● Uses only a few extra variables (min, i, j).

● No additional array required.

✅ Space Complexity = O(1)
✅ It is an In-Place Sorting Algorithm.

⚖️Stability
 ● ❌ Selection Sort is NOT a Stable Algorithm.

🔸 Example:
5A, 2, 3, 5B, 1

● Initially, 5A comes before 5B.

● After sorting:
1, 2, 3, 5B, 5A

● The relative order of equal elements (5A, 5B) changes.

➡️Therefore, Selection Sort is unstable.

📋 Summary Table
Property Description

Type Comparison-based sorting

Approach Repeatedly selects the minimum

element
Best Case Time O(n²)

Average Case O(n²)

Time
Worst Case Time O(n²)

Number of Swaps O(n)

Space Complexity O(1)

In-place Algorithm ✅ Yes

Stable Algorithm ❌ No

🌟 Advantages
● Simple and easy to implement.
 ● Performs fewer swaps than bubble or insertion sort.

● Works well for small datasets.

⚠️Disadvantages
● Inefficient for large datasets due to O(n²) comparisons.

● Not stable, so order of equal elements may change.

● Performance is same in all cases (no improvement for sorted data).

📘 Counting Sort – Notes

L-3.10: Counting Sort | Easiest explanation with example

🔹 Introduction
● Counting Sort is a non-comparison-based sorting algorithm.

● Unlike Quick Sort, Merge Sort, Selection Sort, or Bubble Sort, which compare
elements, Counting Sort works by counting occurrences of elements.

● Other non-comparison-based algorithms include Radix Sort and Bucket Sort.

🔹 Key Idea
● Counting Sort sorts elements by counting the frequency (number of occurrences) of
each distinct element in the input array.

● It works efficiently when the range (K) of input elements is not significantly greater than
the number of elements (N).

● Important Condition: Elements must be within a known range (e.g., 1 to 5).

○ Example: If range = 1–5 → elements can only be 1, 2, 3, 4, or 5.

🔹 Algorithm Steps
1. Input

● Two inputs are given:

1. Array (A) containing numbers to be sorted.

2. Range (K) specifying the maximum possible value of elements.

Example:

A = [2, 1, 2, 3, 1, 2, 4]
Range K = 5

2. Create a Count Array

● Create an auxiliary array C of size K (range).

Initialize all values to 0.

C = [0, 0, 0, 0, 0] → for elements [1, 2, 3, 4, 5]

3. Count Occurrences
Traverse the input array A and record how many times each element appears in C.

Example traversal:

A = [2, 1, 2, 3, 1, 2, 4]
After counting:

C[1] = 2 (1 appears 2 times)

C[2] = 3 (2 appears 3 times)
C[3] = 1 (3 appears once)
C[4] = 1 (4 appears once)
C[5] = 0 (5 doesn’t appear)
→ Count array:

C = [2, 3, 1, 1, 0]

4. Construct the Sorted Array

● Traverse the count array C sequentially.

For each index i, write that number in the output array as many times as it occurred.

Output array:

Sorted = [1, 1, 2, 2, 2, 3, 4]

✅ Array is now sorted.

🔹 Visualization Example
Ste Input Count Array (Occurrences) Output
p
1 [2, 1, 2, 3, 1, 2, 4] [0, 0, 0, 0, 0] —

2 Count [2, 3, 1, 1, 0] —
occurrences
3 Construct output — [1, 1, 2, 2, 2, 3, 4]

🔹 Time Complexity
Counting Sort’s time complexity depends on:

● N → Number of elements in input array

● K → Range of input elements

Formula:
Time Complexity=O(N+K)\text{Time Complexity} = O(N + K)Time Complexity=O(N+K)

Explanation:

● O(N) → Traversing input array to count occurrences.

● O(K) → Traversing count array to construct sorted output.

🔹 Space Complexity
Space Complexity=O(K)\text{Space Complexity} = O(K)Space Complexity=O(K)

● Because an extra array of size equal to the range (K) is used to store counts.

🔹 Advantages
✅ Works in linear time (O(N + K)) for small range values.
✅ Stable algorithm — maintains the relative order of equal elements.
✅ Very efficient when the range is small and known.

🔹 Disadvantages
❌ Range must be known in advance.
❌ Not efficient for large ranges — requires extra memory.

● Example: If one element is 20,000, then array size for counting must be
20,000.
❌ Works only for integers or discrete values (not floating-point or strings directly).

🔹 When to Use Counting Sort

● When:

○ The range (K) is small relative to the number of elements (N).

○ The range is predefined or easily computable.

Baye’s Thoerem:
Bayes Theorem Explained with Solved Example in Hindi ll Machine Learning Course

Slide 1: Spam Detection and Filtering Example

● Overview:
This example demonstrates how to detect and filter spam emails using machine
learning.

● Steps in the Process:

1. Collect emails: Gather a set of emails that we want to analyze for spam filtering.

2. Examine each email: Mark each email as spam or not spam based on specific
criteria.

3. Identify words: Identify keywords that help in classifying the emails as spam or
not spam.

4. Create a list of markers: Collect these keywords that serve as markers for spam
detection.

5. Threshold: Decide on a threshold value to declare an email as spam based on

the presence of these markers.

● Example Use of Bayes' Theorem:

The Bayes' technique is then used to develop a spam detector and filter based on the
presence of specific markers.

Slide 2: Bayes' Theorem

● Formula:
Bayes' Theorem provides a way to calculate the probability of an event given
prior knowledge.
P(A∣B)=P(B∣A)×P(A)P(B)P(A|B) = \frac{P(B|A) \times P(A)}
{P(B)}P(A∣B)=P(B)P(B∣A)×P(A)
○ P(A): The probability of event A occurring.

○ P(B): The probability of event B occurring.

○ P(A|B): The conditional probability of event A occurring given event B occurs.

 ○ P(B|A): The conditional probability of event B occurring given event A occurs.

● Application in Spam Detection:

We use this to calculate the probability that an email is spam based on the occurrence
of certain keywords.

● Example:
We define a threshold for spam. If the probability of spam is greater than 50%, the email
is flagged as spam.

Slide 3: Step 1 – Email Collection for Training

● Objective:
Collect emails to use them for training the machine learning model.

● Dataset Example:
We have a set of 8 emails, out of which 5 are spam and 3 are not.
Each email is labeled as spam or not spam.

● Data Summary:

○ Number of Spam emails: 5

○ Number of Not Spam emails: 3

○ Total emails: 8

Slide 4: Step 2 – Dictionary Preparation

● Objective:
Prepare a dictionary of all words present in the emails.

● Action:
Count the occurrences of each word in the emails and normalize them (e.g., "send"
appears 3 times, "your" appears 4 times).

● Example:
A dictionary might contain words like:

○ "send" = 3

○ "your" = 4
Text
○ "account" = 3
 ○ "report" = 1
and so on for all unique words in the emails.

Slide 5: Step 3 – Calculating Word Probabilities (Detailed Explanation)

Objective:
In this step, we aim to calculate the probability of each word occurring in spam emails. This
helps us understand how likely it is for a given word to appear in a spam email. By calculating
these probabilities, we can later use them to assess whether an email is spam or not.

Formula:
To calculate the probability of a word given that an email is spam, we use the following formula:

P(word∣Spam)=Count of word in Spam emails+1Total words in Spam

emails+Vocabulary sizeP(\text{word}| \text{Spam}) = \frac{\text{Count of word in
Spam emails} + 1}{\text{Total words in Spam emails} + \text{Vocabulary
size}}P(word∣Spam)=Total words in Spam emails+Vocabulary sizeCount of word in
Spam emails+1

Breaking down the formula:

● Count of word in Spam emails:

This is how many times the word appears in the spam emails. For example, if the word
"send" appears 3 times in spam emails, then this count is 3.

● Total words in Spam emails:

This is the total number of words across all the spam emails in our training dataset. If
you have 5 spam emails and each email has 10 words, the total word count would be 50
words.

● Vocabulary size:
This is the number of unique words (the different words) in your entire dataset (spam
+ not spam emails). For example, if there are 10 unique words, then the vocabulary size
is 10.
 ● +1 (Laplace Smoothing):
The "+1" is used to avoid a zero probability for any word that doesn't appear in the
spam emails. If a word is missing from a spam email, it would have a zero probability,
which can be problematic for calculations. Adding 1 ensures that all words, including
unseen ones, are treated fairly.

Example Calculation for the word "send":

Let’s apply the formula to calculate the probability of the word "send" appearing in spam
emails.

Given the following data:

● Count of the word "send" in spam emails = 3

● Total words in spam emails = 18 (total of all words across all spam emails)

● Vocabulary size = 10 (number of unique words across all emails)

We can plug these values into the formula:

P(send∣Spam)=3+118+10=428=0.166P(\text{send}| \text{Spam}) = \frac{3 + 1}

{18 + 10} = \frac{4}{28} = 0.166P(send∣Spam)=18+103+1=284=0.166

So, the probability of the word "send" appearing in a spam email is 0.166 or 16.6%.

Slide 6: Step 4 – Calculating Spam Probability for an Email

● Objective:
Calculate the overall probability that an email is spam given the probabilities of
 individual words (using Bayes' Theorem).

● Formula:
P(Spam∣Email)=P(Spam)×P(word1∣Spam)×P(word2∣Spam)×…P(Spam|
Email) = P(Spam) \times P(\text{word1}|Spam) \times P(\text{word2}|Spam)
\times \dotsP(Spam∣Email)=P(Spam)×P(word1∣Spam)×P(word2∣Spam)×…
● Example:
P(Spam∣Email)=0.625×0.166×0.166×⋯=0.0172P(Spam|Email) = 0.625 \
times 0.166 \times 0.166 \times \dots =
0.0172P(Spam∣Email)=0.625×0.166×0.166×⋯=0.0172
This is the probability that the email is spam.

✅ Explanation:

● P(Spam)P(\text{Spam})P(Spam) = Prior probability that any email is spam

● P(word∣Spam)P(\text{word} \mid \text{Spam})P(word∣Spam) = Probability

that each word appears in spam emails

● The product of these values gives the likelihood that the email is spam based on its
words.

● Decision:
If the calculated probability is higher than the threshold (e.g., 50%), the email is
classified as spam. If it is lower, it is classified as not spam.

SVM:
Lec-40: Support Vector Machines (SVMs) | Machine Learning

Slide 1: Spam Detection Process Overview

This slide introduces the process of spam detection in emails. Here's how it works:

1. Collect Emails: You gather a set of emails.

2. Examine Emails: Examine each email and identify if it is spam or not.

 3. Identify Keywords: Find specific words in the email that help identify whether it's spam
or not. For example, "free" could be a marker for spam.

4. Create a List: Collect all such keywords (markers) that identify an email as spam or not.

5. Threshold: Decide on a threshold—how many markers (such as certain words) are

needed to label an email as spam.

The SVM (Support Vector Machine) algorithm is used to find the optimal boundary
(hyperplane) to separate these two classes—spam and not spam. It uses the words in the email
(like "free" or "gift") to distinguish between the two classes.

Slide 2: Training Dataset

In this slide, you are shown how a dataset is prepared for training the spam filter.

● Example Dataset: The dataset contains messages labeled as either "spam" or "not
spam." Each message is labeled so the algorithm can learn what spam and non-spam
emails look like.

● Sample Messages:

○ "Congratulations! You've won a free gift card." (Spam)

○ "Can we meet tomorrow at 5?" (Not Spam)

○ "Get a free subscription now!" (Spam)

○ "Are you coming to the party tonight?" (Not Spam)

This dataset will be used by the model to understand which words are commonly found in spam
versus non-spam emails.

Slide 3: Feature Extraction (TF-IDF)

This slide explains how to convert text data (like email messages) into numbers that a machine
learning algorithm can understand.

● TF-IDF stands for Term Frequency - Inverse Document Frequency.

○ Term Frequency (TF): How often a word appears in a document.

 ○ Inverse Document Frequency (IDF): Measures how unique or rare a word is
across all documents.

By multiplying TF and IDF, you get the TF-IDF score, which represents the importance of a
word in a document. This helps in converting emails into numeric vectors (lists of numbers) that
the machine learning model can use.

Slide 4: Message Vectorization

Here, the slide explains how messages are converted into vectors (numbers).

● We are using the keywords "free" and "meeting."

● Presence or Absence: The emails are converted into vectors based on whether they
contain the words "free" or "meeting."

○ For example, if a message contains the word "free," it gets a 1 (indicating "yes").

○ If the
○
○ message doesn’t contain the word "meeting," it gets a 0 (indicating "no").

Example:

● "Win a free prize now": Contains "free" → [1, 0]

● "Let's schedule a meeting": Contains "meeting" → [0, 1]

This step turns each email into a format that SVM can use.

Slide 5: Calculating TF-IDF

Here, you see the formula for TF and IDF.
Support Vector Machines (SVM) – Key Concepts
● Definition:
SVM is a supervised machine learning algorithm used for both classification and
regression tasks. It works by separating data into different classes using a decision
boundary called a hyperplane.

Important Terms
 ● Hyperplane:
A decision boundary that separates data points of different classes.
For example, in an email spam classification, a hyperplane might separate "spam" and
"not spam."

● Margin:
The distance between the hyperplane and the nearest data point from either class.
Goal: Maximize the margin for better separation.

● Support Vectors:
The data points closest to the hyperplane that influence its position. These points are
crucial for defining the boundary.

Example:
● f(n) = 5n + 3

○ For large values of n, f(n) behaves like 5n.

○ Using constants, we can say f(n) = Θ(n), meaning f(n) grows proportionally to
n.

Types of Margins
1. Hard Margin:
Data can be perfectly separated by a hyperplane (no overlap).

2. Soft Margin:
Data can't be perfectly separated; some points might overlap or fall inside the margin.

Linear vs Non-linear Separation

● Linear Kernel: Used if data is already separable in its original form.

● Non-linear Kernels (e.g., Polynomial, Radial Basis Function): Used to increase the
dimensions of the data, making it easier to separate.

Key Takeaways:
● SVM aims to maximize the margin for better classification.

● Support vectors help in defining the hyperplane.

● If data isn't linearly separable, SVM uses kernel functions to map data into higher
dimensions and make it separable.

In short:
SVM separates data using a hyperplane, and the goal is to maximize the margin for better
accuracy. Support vectors are crucial, and kernels help when the data isn't linearly separable.
TF-IDF Explained with Solved Example in Hindi l Natural Language Processing

Greedy Algorithms – Introduction (Notes)

L-4.1: Introduction to Greedy Techniques With Example | What is Greedy Techniques

1. Definition
● Greedy Algorithm (or Greedy Technique):
An algorithmic approach that selects the best local (immediate) choice at each step
with the hope of finding a global optimum.

Key Idea:
“Choose the best option available at the moment (locally optimal), expecting it will
lead to the best overall solution (globally optimal).”

2. Concept Explanation
● At each stage, the algorithm makes a choice that looks best at that moment.

● It does not reconsider its choices later.

● There is no guarantee that the final result will be globally optimal, but for many
problems, it gives the correct or near-optimal solution.

3. Example Explanation (Path Cost Example)

● Suppose we have a source node and multiple paths leading to a destination.

● Each path has a cost:

○ Path A: 10

○ Path B: 20

○ Path C: 5

● The Greedy algorithm will choose the path with the lowest cost (5) at this stage.
 ● This decision is local (based only on current data), aiming for global optimality
(minimum total cost).

4. Terminologies
a) Solution Space
● All possible options or solutions to a problem.
Example: All career options after school — Engineering, Medical, Banking, Business,
etc.

b) Feasible Solution
● Solutions that satisfy some constraints or selection criteria.

○ Example: If you studied Arts, Engineering is not feasible.

c) Optimal Solution
● The best feasible solution according to a particular goal:

○ Minimum cost

○ Maximum profit

○ Minimum risk

5. Real-Life Analogy
Career Choice Example:
● Solution Space: All possible career options.

● Feasible Solutions: Based on qualifications (arts, science, commerce, etc.).

● Optimal Solution: Chosen based on personal goals (e.g., least cost, maximum salary,
minimum risk).
Offer Example (Shopping Analogy):
● During sales, we tend to choose the store offering maximum discount (maximum profit)
regardless of quality.

● That is local optimization — the “greedy” behavior.

6. What Greedy Algorithm Focuses On

Objective What Greedy
Chooses
Cost Minimum cost

Profit Maximum profit

Risk Minimum risk

7. Important Note
● Greedy algorithms do not guarantee a global optimum in every case.

● They work well only when a local optimum leads to a global optimum.

8. Common Problems Solved Using Greedy Algorithms

Problem Objective

Knapsack Problem Maximize profit / value

Job Sequencing Problem Maximize profit

Minimum Cost Spanning Tree Minimize cost

Optimal Merge Pattern Minimize merge cost

Huffman Coding Minimize total code length

Dijkstra’s Algorithm Find shortest path (minimum cost)

○ Add this item to the bag and check the

remaining capacity.
 ○ Issue: After adding the most profitable item,
the remaining bag capacity might not
accommodate the other items fully.

2. Greedy by Weight:

○ This approach picks the lightest item first to

make room for more items.

○ Example: Start with Object 3 (lightest) with

weight 10, add it to the bag, then select the
next smallest item.

○ Issue: This does not always maximize the

profit.

3. Greedy by Profit/Weight Ratio (Optimal approach):

○ Calculate the profit-to-weight ratio for each

item.

■ Example: Object 1 has a ratio of 25/18

= 1.39.

○ Sort items by this ratio and select the items

accordingly.

1. Greedy Algorithm Introduction

● Definition: The greedy algorithm builds a solution step by step. At each step, it chooses
the best immediate option, aiming for the most obvious and immediate benefit.

● Usage: Primarily used for optimization problems where you try to find the best solution
quickly.

Examples of Greedy Algorithms:

● Fractional Knapsack

● Dijkstra’s Algorithm

● Kruskal’s Algorithm

● Huffman Coding
 ● Prim’s Algorithm

2. Characteristics of Greedy Algorithm

● Simple: Easy to understand and implement.

● Efficient: Works quickly, often in time complexity that is linear or logarithmic.

● Fast Solutions: Provides quick solutions but not always the best or optimal ones.

● No Backtracking: Once a decision is made, it’s final; the algorithm doesn’t reconsider.

● Based on Current Info: It makes choices based on available information at that time,
without considering future consequences.

Note: While greedy algorithms work well in many cases, they are not always optimal for all
problems, as shown in some examples.

3. How Does the Greedy Approach Work?

Steps:

1. Start with the initial problem and make choices.

2. Evaluate all possible choices from that point in time.

3. Pick the best option at that moment, even if it’s not the best in the long term.

4. Move to the next step based on the chosen option, and continue until the problem is
solved.

Key Idea: The algorithm makes the best choice at each step without considering future
consequences. It’s a quick, but not always the most accurate, approach.

4. Coin Change Problem Example

● Goal: Minimize the number of coins used to pay a total of 39 using available coin
denominations ([1, 2, 5, 10]).

Steps:
1. Start with the highest coin denomination that’s less than or equal to the amount. The
largest coin for 39 is 10.

2. Subtract the coin value from the total amount and add it to the solution (e.g., 39 - 10 =
29).

3. Repeat until the amount to be paid is 0.

6. Greedy Algorithm Conclusion
● Greedy Algorithms: Effective for optimization problems like the Coin Change
problem, Fractional Knapsack, and Dijkstra’s Shortest Path.

● Speed: They are fast but not always optimal.

● Non-Revisitable Choices: Once a decision is made, it’s not revisited, which makes
them less flexible.

● Limitation: The algorithm might fail if making a locally optimal choice blocks access to
a better long-term solution.

Final Thoughts: Greedy algorithms are great for quick solutions, but they might not always
lead to the best result for every problem.
Knapsack Problem – Notes
L-4.2: Knapsack Problem With Example| Greedy Techniques| Algorithm

Definition:

● The Knapsack Problem is a common optimization problem where:

○ You are given a set of items, each with a profit and weight.

○ You also have a bag (knapsack) with a weight capacity.

○ The goal is to maximize the profit by selecting a combination of items such that
their total weight does not exceed the bag's capacity.

Problem Statement:

● We are given:

○ 3 items with their profits and weights.

○ The capacity of the bag is 20.

○ The goal is to maximize the total profit while keeping the total weight within the
limit of 20.

Greedy Technique:

● Greedy Approach means always selecting the best immediate option, based on the
current information, without considering future consequences.

Three Approaches:

4. Greedy by Profit:

○ First, pick the item with the highest profit.

○ Example: The item with the highest profit is Object 1, with a profit of 25.

○ Example:

■ Object 1: Profit/Weight = 25/18 = 1.39

■ Object 2: Profit/Weight = 24/15 = 1.6

■ Object 3: Profit/Weight = 15/10 = 1.5

 ○ Optimal Result: By considering both profit and weight, this method gives the
best possible solution (profit = 31.5).

Algorithm Steps:

1. Calculate Profit-to-Weight Ratio for each item.

2. Sort Items based on their ratio (highest to lowest).

3. Select Items:

○ Add items to the knapsack starting with the highest ratio, until the bag's capacity
is filled.

Time Complexity:

● Calculating the ratio and sorting the items takes O(n log n) time.

● Therefore, the overall time complexity is O(n log n).

Conclusion:

● The Greedy Algorithm is effective but may not always provide the best solution unless
both profit and weight are considered.

● Using the profit-to-weight ratio method gives the optimal solution for the knapsack
problem.

Summary:
● Knapsack Problem: Maximize profit while staying within weight limit.

● Greedy Techniques:

○ Greedy by Profit: Pick highest profit first.

○ Greedy by Weight: Pick lightest item first.

○ Greedy by Profit/Weight Ratio: Optimal approach.

● Optimal Approach: Calculate Profit/Weight Ratio, sort, and select items accordingly.

Huffman Coding:
L-4.3: Huffman Coding Algorithm in Hindi with Example | Greedy Techniques(Algorithm)
L-4.4: Huffman Coding Question in Greedy Technique | Imp Question for all competitive exams

Spanning Tree – Notes

L-4.7: What is Spanning Tree with Examples in Hindi | Algorithm

Definition:

● A spanning tree of a graph is a connected subgraph that includes all the vertices of
the original graph without any cycles.

● A spanning tree contains:

○ All vertices of the graph.

○ V-1 edges, where V is the number of vertices in the graph.

○ No cycles (it's a tree).

Key Properties of a Spanning Tree:

1. Connected:

○ All vertices in the graph must be reachable. No isolated vertices.

2. No Cycles:

○ A spanning tree cannot have cycles. It is acyclic.

3. Contains all vertices:

○ A spanning tree includes every vertex of the original graph.

4. V-1 edges:

○ A spanning tree will always have one fewer edge than the number of vertices,
i.e., if there are 4 vertices, the tree will have 3 edges.

Example:

● Given a graph with 4 vertices:

○ Vertices: 1, 2, 3, 4.

○ Edges: E1, E2, E3, etc.

 ○ Capacity of the bag: 20 units.

● A spanning tree of this graph must include all 4 vertices and exactly 3 edges. You can
form multiple spanning trees for a single graph, depending on the way you connect the
edges.

Types of Spanning Trees:

● There can be multiple spanning trees for a single graph. For example, with 4 vertices,
you can create different spanning trees by connecting the vertices in different ways.

Spanning Tree of Complete Graph (K4):

● For a complete graph with 4 vertices (K4), there are 16 possible spanning trees.

○ Formula to calculate the number of spanning trees in a complete graph: N^(N-2)

where N is the number of vertices.

○ For example, for K4, N = 4, so the number of spanning trees = 4^(4-2) = 4^2 =
16.

Formula for Spanning Trees in Complete Graph:

● N^(N-2): This is used when you have a complete graph and want to calculate the
number of possible spanning trees.

○ Example for K5: For 5 vertices, 5^(5-2) = 5^3 = 125 spanning trees.

Algorithms for Minimum Cost Spanning Tree:

● Two popular algorithms used to find the minimum cost spanning tree are:

1. Kruskal’s Algorithm

2. Prim’s Algorithm

● These algorithms are crucial in the greedy technique and are commonly used for
finding minimum cost spanning trees.

Conclusion:

● Spanning trees are essential for solving optimization problems in graphs.

● Greedy algorithms like Kruskal’s and Prim’s are used to find the minimum cost
spanning tree.
 ● For complete graphs, the number of possible spanning trees can be calculated using
the formula N^(N-2).

Summary:
● A spanning tree is a connected, acyclic subgraph with all vertices and V-1 edges.

● Multiple spanning trees are possible for a given graph.

● For complete graphs, use the formula N^(N-2) to find the number of spanning trees.

● Kruskal's and Prim's algorithms are used to find the minimum cost spanning tree.

Kruskal’s Algorithm – Notes

L-4.8: Kruskal Algorithm for Minimum Spanning Tree in Hindi | Algorithm

Introduction:

● Kruskal’s Algorithm is used to find the minimum cost spanning tree (MST) of a
graph.

● It is a greedy algorithm that selects the edges with the minimum weight first, ensuring
that no cycles are formed.

Key Properties of Spanning Tree:

1. Number of vertices: The number of vertices in the spanning tree is the same as in the
original graph.

2. Number of edges: A spanning tree will always have V - 1 edges (where V is the
number of vertices).

3. No cycles: The spanning tree must not have any cycles.

4. Connectivity: The spanning tree should be connected, meaning all vertices should be
reachable.

Steps for Kruskal's Algorithm:

1. Sort the edges of the graph in increasing order of their weights.

2. Pick the smallest edge. Add it to the spanning tree if it doesn't form a cycle.
 3. Repeat the process: Continue selecting the smallest edge that does not form a cycle
until you have V-1 edges (where V is the number of vertices in the graph).

Example:

● Given a graph with vertices 1, 2, 3, 4, 5, 6, 7, and edges with weights.

● Start by sorting the edges in increasing order and pick the smallest edge that doesn’t
form a cycle.

● If you have edges like B-E (weight 2), A-C (weight 3), and so on, select the minimum
one and continue adding edges without forming any cycles.

● The final minimum cost spanning tree will have 6 edges (for 7 vertices), and the sum
of weights will give the minimum cost.

Important Concepts:

1. Disconnected Intermediate Result: In Kruskal’s algorithm, the result at each

intermediate step can be disconnected, but the final result will always be a connected
spanning tree.

2. Cycle Check: Even if an edge has the minimum weight, it is not included if it forms a
cycle.

Time Complexity:

● The time complexity depends on sorting the edges:

○ If using a Min-Heap, the complexity is O(E log E), where E is the number of
edges.

○ In the best case, if there are N-1 edges (where N is the number of vertices), the
time complexity is O(N log E).

○ In the worst case, you might need to check all edges, so the time complexity is
O(E log E).

Conclusion:

● Kruskal's algorithm is efficient for finding the minimum cost spanning tree in a graph.

● The algorithm is based on greedy principles: it always chooses the minimum weight
edge first and avoids cycles.

● It is simple and easy to implement, especially when the edges are already sorted.
 ● The time complexity is O(E log E), which can be improved using Min-Heaps for edge
sorting.

Summary:
● Kruskal's Algorithm: Used to find the minimum cost spanning tree in a graph.

● Steps: Sort edges by weight, pick the smallest edges, and avoid cycles until you have V-
1 edges.

● Time Complexity: O(E log E).

● Cycle Check: Ensure no cycles are formed during edge selection.

Prim’s Algorithm – Notes

L-4.9: Prim's Algorithm for Minimum Cost Spanning Tree | Prims vs Kruskal

Introduction:

● Prim’s Algorithm is used to find the minimum cost spanning tree (MST) in a
weighted, undirected graph.

● It works by adding the shortest edges to the tree in a way that the tree remains
connected and does not form cycles.

Key Concepts:

1. Spanning Tree:

○ A spanning tree includes all the vertices of the graph and has exactly V-1 edges
(where V is the number of vertices).

○ It must be connected and acyclic (no cycles).

2. Minimum Cost Spanning Tree:

○ The goal is to find the spanning tree with the least total edge weight.

Steps of Prim’s Algorithm:

1. Start from any vertex: Choose any vertex as the starting point. If the starting vertex is
provided, begin from there.
 2. Select the smallest edge: From the chosen vertex, pick the smallest edge (with the
least weight) that connects it to an unvisited vertex.

3. Repeat the process: Add the smallest edge from the tree to the unvisited vertices,
ensuring no cycles are formed.

4. Stop when: You have added V-1 edges (where V is the number of vertices) to the tree.

Detailed Working Example:

1. Start with vertex B:

○ Check the connected edges: B-A (weight 1) and B-C (weight 6). Pick the edge
with the minimum weight (B-A).

2. Add vertex A to the tree:

○ From A, check the connected edges: A-D (weight 5) and A-B (already chosen).
Pick A-D (weight 5).

3. Add vertex D to the tree:

○ From D, check the connected edges: D-F (weight 2), D-C (weight 6), and D-B
(already chosen). Pick D-F (weight 2).

4. Add vertex F to the tree:

○ From F, check the connected edges: F-C (weight 3), F-D (already chosen).
Pick F-C (weight 3).

5. Continue the process: Add the remaining vertices and edges until all vertices are
included in the tree.

Key Points:

● Greedy Choice: Always pick the smallest edge that connects an unvisited vertex to the
growing spanning tree.

● No Cycles: Ensure no cycles are formed while adding edges.

● Connected Tree: Keep the tree connected as you add edges.

Time Complexity:

● The time complexity of Prim’s Algorithm is O(E log V) (where E is the number of edges
and V is the number of vertices).
 ○ Using Min-Heap: The algorithm can be optimized using a Min-Heap for edge
selection, making it more efficient.

Summary:

● Prim’s Algorithm is a greedy algorithm to find the minimum cost spanning tree.

● It works by starting from any vertex and adding the minimum weight edge at each step,
ensuring the tree remains connected and acyclic.

● The time complexity is O(E log V) when using efficient data structures like Min-Heaps.

Important Tips:
● Cycle Check: Always make sure that adding an edge doesn’t form a cycle.

● Greedy Property: Prim’s algorithm makes locally optimal choices at each step, aiming
for a globally optimal solution.

● The result from Prim’s will be the same as Kruskal's algorithm in terms of the
minimum spanning tree, though the approaches differ.

Dijkstra's Algorithm – Notes

L-4.10: Dijkstra's Algorithm - Single Source Shortest Path - Greedy Method

Introduction:

● Dijkstra's Algorithm is used to find the shortest path from a single source vertex to
all other vertices in a weighted graph.
 ● It is a greedy algorithm that gives the minimum cost path.

● Commonly used in network routing (e.g., Google Maps, social networking, DNA
mapping).

Key Concepts:

1. Single Source Shortest Path:

○ The algorithm finds the shortest path from a single source vertex to all other
vertices.

○ The graph must have non-negative edge weights.

2. Greedy Approach:

○ The algorithm always selects the minimum weight edge to progress towards
the next vertex, ensuring optimal solution.

3. Relaxation:

○ Relaxation is the core of Dijkstra’s algorithm. It means updating the shortest

distance for a vertex if a shorter path is found.

○ Distance of a vertex is updated based on the shortest known path.

4. Spanning Tree:

○ The final result is a shortest path spanning tree rooted at the source.

Algorithm Steps:

1. Initialization:

○ Set the distance of the source vertex to 0 and all other vertices to infinity.

○ Mark all vertices as unvisited.

2. Relaxation:

○ From the source, examine all neighboring vertices. If a shorter path is found,
update the distance.

○ Repeat this process for all vertices, ensuring that the shortest paths are always
chosen.

3. Continue:
 ○ Always choose the unvisited vertex with the smallest tentative distance.

○ Mark it as visited and update its neighbors.

4. Stop when all vertices have been visited.

Example (for a graph with 6 vertices):

1. Start from source: Vertex 1. Initialize the distances:

○ Distance from 1 to 1 = 0, all others = infinity.

2. Relax edges:

○ From 1 to 2: Distance = 7.

○ From 1 to 3: Distance = 9.

○ From 1 to 6: Distance = 14.

3. Choose next smallest distance: Vertex 2 (cost 7).

○ Update distances from 2.

4. Repeat the process until all vertices have the shortest path known.

Key Points:

● Connected Graph: The algorithm works on connected graphs where there is a path
from the source to every other vertex.

● Non-Negative Weights: Works only if all edge weights are non-negative.

Time Complexity:

● Using Min-Heap: O(E log V) (where E is the number of edges, and V is the number of
vertices).

● Without Min-Heap: O(V²).

Disadvantages:

● Negative Weight Edges: Dijkstra's algorithm does not work if the graph contains edges
with negative weights.

Example of Dijkstra’s Algorithm (Summary):

 ● Graph: Vertices: 1, 2, 3, 4, 5, 6.

● Edges: Distances between vertices (e.g., 1 to 2 = 7, 1 to 3 = 9).

● Process: Start from vertex 1, update the shortest paths to 2, 3, 6, etc., and stop when all
vertices are visited.

Conclusion:

● Dijkstra's algorithm is ideal for finding the shortest path in a graph with non-negative
weights.

● It uses a greedy approach and works efficiently with a Min-Heap.

● Time complexity: O(E log V).

Dijkstra's Algorithm – Notes

L-4.11: Dijkstra's Algorithm Analysis | Time Complexity | Pseudocode Explanation

What is Dijkstra's Algorithm?

● Dijkstra's algorithm finds the shortest path from a single source vertex to all other
vertices in a graph with non-negative weights.

● It is used for single source shortest path problems and works on both directed and
undirected graphs.

● Real-life example: Google Maps, where you need to find the shortest path from a
source location to all other possible destinations.

Key Concepts:

1. Graph Representation:

○ Vertices (Nodes): Points connected by edges.

○ Edges (Connections): Have weights (cost, distance, time, etc.).

○ Directed or Undirected: Dijkstra’s works with both.

2. Greedy Approach:

○ The algorithm follows a greedy approach where it repeatedly selects the

shortest path available to minimize the overall cost.

3. Relaxation:
 ○ Relaxation is the process of updating the shortest distance of a vertex. If a
shorter path is found, update the distance.

Algorithm Steps:

1. Initialize:

○ Set the distance from the source to itself as 0, and all other vertices to infinity.

2. Heap Construction:

○ Use a min-heap to store vertices based on their distance values.

3. Extract Minimum:

○ Extract the vertex with the minimum distance from the heap.

4. Relaxation:

○ For each neighboring vertex, update the distance if a shorter path is found.

5. Repeat:

○ Continue the process until all vertices are visited.

Example:

● Graph:

○ Vertices: {1, 2, 3}

○ Edges with weights: {1-2: 7, 1-3: 9, 2-3: 3}

● Process:

○ Start from vertex 1. Distance to 1 is 0, others are infinity.

○ Relax distances based on neighbors:

■ From 1 to 2: 7, 1 to 3: 9.

■ Extract the minimum distance (vertex 2, distance 7), and update

distances to 3.

○ Continue until the shortest path to all vertices is found.

Time Complexity:
 ● Initial Setup: Set the distance of all vertices to infinity – O(V), where V is the number of
vertices.

● Min-Heap Construction: Building the heap takes O(V).

● Extract Min: Extracting the minimum value from the heap takes O(log V). This is done
for each vertex, so the total time for this operation is O(V log V).

● Relaxation: Relaxing each edge involves checking each neighbor, taking O(E log V)
time, where E is the number of edges.

● Total Complexity: O(E log V) (in general, edges are usually more than vertices, so the
complexity is based on edges).

Disadvantages:

● Negative Weights: Dijkstra’s algorithm does not work with negative weight edges.

● Efficiency: While it is efficient for graphs with non-negative weights, it may not be the
best choice for graphs with negative weights or very dense graphs.

Conclusion:

● Dijkstra's algorithm is a greedy algorithm for finding the shortest path in graphs with
non-negative weights.

● Time complexity: O(E log V), where E is the number of edges and V is the number of
vertices.

Graph Traversal Methods: BFS & DFS - Notes

L-4.15: BFS & DFS | Breadth First Search | Depth First Search | Graph Traversing | DAA

Graph Traversal

● Definition: The process of visiting and exploring a graph (or tree) for processing.
Involves two main tasks:

○ Visiting a vertex.

○ Exploring its neighbors (adjacent vertices).

● Tree vs. Graph:

○ Every tree is a graph, but not every graph is a tree (graphs can have cycles,
trees cannot).
1. Breadth-First Search (BFS)
● Method: BFS explores the graph level by level, visiting all nodes at the current level
before moving to the next.

○ Queue Data Structure: FIFO (First In First Out) is used to keep track of nodes.

● Working:

○ Start from a node (e.g., node 1).

○ Add adjacent nodes (neighbors) to the queue.

○ Visit and explore all the neighbors before moving to the next level.

○ Repeat until all vertices are visited.

● Example:

○ Start at node 1, visit neighbors 2 and 3.

○ Then visit neighbors of 2 and 3, and so on.

● Real-Life Example: Like exploring all food stalls at a food court: you visit each stall on
the same level before moving to the next row of stalls.

● Time Complexity: O(V + E) where:

○ V = number of vertices.

○ E = number of edges.

2. Depth-First Search (DFS)

● Method: DFS explores as deep as possible along one branch before backtracking to
explore other branches.

○ Stack Data Structure: LIFO (Last In First Out) is used to keep track of nodes.

● Working:

○ Start at a node (e.g., node 1).

○ Explore one neighbor (deep dive).

 ○ If no more neighbors, backtrack to the last node with unexplored neighbors.

○ Continue until all vertices are visited.

● Example:

○ Start at node 1, go deep to node 2, then to node 4, and so on. If no further

nodes, backtrack and explore other paths.

● Real-Life Example: Like choosing a career path and sticking to it until you hit a dead
end, then backtracking to explore other options.

● Time Complexity: O(V + E) where:

○ V = number of vertices.

○ E = number of edges.

Key Differences Between BFS and DFS

1. Traversal Method:

○ BFS: Explores level by level, breadth-first.

○ DFS: Explores deep down one path, backtracks when necessary.

2. Data Structure Used:

○ BFS: Uses a queue (FIFO).

○ DFS: Uses a stack (LIFO).

3. Backtracking:

○ BFS: No backtracking, level-by-level exploration.

○ DFS: Backtracking is essential when a path is fully explored.

4. Graph Exploration:

○ BFS: Can be more useful when the graph is large or you need the shortest path
in an unweighted graph.

○ DFS: Often used for tasks like topological sorting or checking connectivity.
Applications:
● BFS:

○ Shortest path in unweighted graphs.

○ Social networking and web crawling (finding nearest connections).

● DFS:

○ Solving puzzles (e.g., mazes, sudoku).

○ Finding connected components in a graph.

Conclusion:
● BFS is better for level-order traversal, while DFS is better for deep explorations.

● Both algorithms are important in computer science and have many practical
applications, such as in network routing, web crawlers, and social media connections.

Dynamic Programming - Notes

L-5.1: Introduction to Dynamic Programming | Greedy Vs Dynamic Programming |
Algorithm(DAA)

Introduction

● Dynamic Programming (DP) is used to solve optimization problems. These problems

aim to find the maximum or minimum value, such as:

○ Maximum profit or Minimum cost.

● Difference from Greedy Approach:

○ Greedy Algorithm makes decisions based on the current situation (local

optimum), which may not always lead to the global optimum.

○ Dynamic Programming considers all possibilities, solving overlapping

subproblems and guarantees the optimal solution.

Key Concepts in Dynamic Programming

 1. Optimal Substructure:

○ Problems can be broken into smaller subproblems, each with an optimal solution.

○ Example: In the Fibonacci sequence, each term is the sum of the previous two
terms. This is the optimal substructure.

2. Overlapping Subproblems:

○ Subproblems are solved multiple times in a naive approach. DP avoids this by

storing results of subproblems and reusing them.

○ Example: In the Fibonacci sequence, f(2) and f(1) are computed multiple
times. DP stores the result to avoid recomputation.

How Dynamic Programming Works

1. Breaking Problems into Subproblems:

○ The problem is divided into smaller subproblems (this is where optimal

substructure comes in).

○ Example: For the Fibonacci sequence, to calculate f(4), we need f(3) and
f(2). We break it down further until the base case.

2. Storing Subproblem Solutions:

○ Once a subproblem is solved, its solution is stored to avoid solving the same
problem again. This leads to overlapping subproblems.

○ Example: We store the results of f(2), f(3), etc., so that we don’t recompute
them multiple times.

3. Constructing the Final Solution:

○ After solving all the subproblems and storing the results, DP combines these
solutions to form the optimal solution for the original problem.

Advantages of Dynamic Programming

● Avoids Repeated Work: By storing solutions to subproblems, DP avoids recomputing
results.
 ● Optimal Solution: Unlike Greedy, DP guarantees the optimal solution.

Applications of Dynamic Programming

● Fibonacci Sequence: Storing the values of f(2), f(3), etc., to avoid recalculating.

● Matrix Chain Multiplication: To find the most efficient way to multiply a series of
matrices.

● 0-1 Knapsack Problem: Solving the problem of selecting items with given weights and
values to maximize profit within a weight limit.

● Longest Common Subsequence: Finding the longest subsequence common to two

sequences.

● Traveling Salesman Problem (TSP): Finding the shortest route that visits all cities once
and returns to the origin city.

● All Pair Shortest Path: Finding the shortest paths between all pairs of nodes in a graph.

Conclusion
● Dynamic Programming solves optimization problems by breaking them down into
overlapping subproblems and storing the solutions to avoid recomputation. It guarantees
an optimal solution, unlike Greedy Algorithms, which might not always give the best
result.

Travelling Salesman Problem (TSP) - Notes

L-5.4: Traveling Salesman Problem | Dynamic Programming

Definition of TSP

● Travelling Salesman Problem (TSP) involves a salesman who must travel through
multiple cities (nodes in a graph), visiting each city once, and return to the starting city,
all while minimizing the total cost (or distance).

● Objective: Find the minimum cost to visit all cities once and return to the starting point.

Approaches to Solve TSP

 1. Greedy Method:

○ Greedy approach selects the next nearest city at each step (locally optimal
choice).

○ Example:

■ Start from city 1, choose the nearest city (cost 10 to city 2).

■ From city 2, choose the next nearest city (cost 10 to city 4), and so on.

○ Problem with Greedy: This method doesn’t always give the optimal solution, as
it may not consider future costs effectively.

○ Result: May give a suboptimal solution (e.g., total cost of 55).

2. Brute Force Method:

○ Brute force: Try all possible city visit combinations and calculate the total cost
for each. The one with the minimum cost is the answer.

○ Example: For 4 cities, evaluate all possible routes and select the one with the
least cost.

○ Result: Can be time-consuming as it evaluates all permutations of cities. Time

complexity: O(N!).

3. Dynamic Programming (DP):

○ Dynamic Programming solves TSP by breaking it into smaller subproblems and

storing the results to avoid recomputation.

○ Challenges: While DP can reduce time complexity, it still cannot convert the
problem into polynomial time. TSP remains an NP-complete problem.

○ Hint for DP: Subproblems must overlap, but in TSP, subproblems are not
entirely overlapping, so DP isn't fully effective for this problem.

Time Complexity

● Greedy Method: Suboptimal results, but fast to compute.

● Brute Force: O(N!) time complexity (factorial), as it evaluates all possible permutations.

● Dynamic Programming: Reduces the time complexity but still remains exponential in
nature for TSP.
Key Insights

● TSP is NP-Complete: This means that no known polynomial-time algorithm can solve
TSP efficiently for large graphs.

● Hamiltonian Cycle: TSP is related to the Hamiltonian cycle, where you need to visit all
nodes exactly once and return to the starting node.

Conclusion

● TSP is a classic optimization problem in graph theory and algorithms. While greedy
methods provide quick, but suboptimal solutions, brute force guarantees the best result
but is computationally expensive. Dynamic programming helps, but doesn’t change the
NP-complete nature of the problem.

Here are simple and clear notes from the transcript:

Heap Tree – Introduction (Gate Smashers Notes)

[Link]
v=uuot9ItgTEI&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=32

1. What is a Heap Tree?

A Heap Tree is a special type of Binary Tree that satisfies two main properties:

● Structural Property

● Ordering Property

2. Structural Property (Shape Property)

● The tree must be an Almost Complete Binary Tree (ACBT).

● Rules of ACBT:

1. Go to the next level only when the previous level is full.

 2. Fill the left child first, then the right child.

📘 Example:
If level 2 is not fully filled and you start filling level 3 → ❌ Not ACBT.

3. Ordering Property
There are two types of heap trees:

1. Max Heap

○ The root node is the maximum element.

○ Parent > Child at every level.

2. Min Heap

○ The root node is the minimum element.

○ Parent < Child at every level.

📘 Example:
Max Heap:

10

/ \

8 7

/\ /\

5 46 3

● Every parent node > its children ✅

Min Heap:

/\

5 7
 /\ /\

8 10 9 11

● Every parent node < its children ✅

4. Important Points
● To check if a tree is a Heap:

1. It must be ACBT (structural check).

2. It must satisfy ordering property (Max or Min Heap).

● If the structural property fails → it’s not a heap, even if ordering is correct.

5. Example Question (GATE level)

Question: Which of the following is a Max Heap?

Options: A, B, C, D

✅ Answer: Option B
 ● It is an ACBT and satisfies Parent > Child.
❌ Others fail structural or ordering property.

6. Upcoming Topics
● Heap Insertion

● Deletion

● Heapsort

● Heapify

● Array Representation of Heap

● Priority Queue

Would you like me to make a shorter one-page exam-style version (with bullet points only)?

🧩 Heap Tree Construction (Gate Smashers Notes)

[Link]
v=KzXpfxRzVQM&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=33

1. What is Heap Tree Construction?

It is the process of creating a heap tree (Max Heap or Min Heap) by inserting elements
following heap properties.
Two main methods are used for construction.

2. Methods of Heap Construction

(a) Insertion Method (One-by-One Key Insertion)

● Insert each key one at a time in the given order.

 ● After inserting each key:

○ Place it according to ACBT (Almost Complete Binary Tree) rules.

○ Compare the inserted node with its parent.

○ Swap if the heap property (Max/Min) is violated.

○ Keep swapping upward until the property is satisfied.

🕒 Time Complexity:

● For one element → O(log n)

● For n elements → O(n log n)

📘 Example (Max Heap):

Insert keys: 14, 24, 12, 11, 25, 8, 35, 45

Process (simplified):

1. Insert 14 → Root (no swap needed)

2. Insert 24 → Compare with parent (14) → Swap → 24 ↑, 14 ↓

3. Insert 12 → No swap needed (parent 24 > 12)

4. Insert 25 → Swap with parent 14 → then swap again with parent 24 → New root
25

5. Continue similarly…

6. Insert 45 → Swaps up through the tree → Becomes new root

✅ Final Max Heap Example:

45

/ \

35 25

/ \ / \

24 14 12 8

/
 11

(b) Heapify Method

● Put all elements into the tree first (as an ACBT).

● Then apply Heapify (adjust the tree from bottom to top).

🕒 Time Complexity: O(n) → Faster than insertion method

3. Key Points

● Insertion method: builds heap step-by-step → O(n log n)

● Heapify method: builds heap in one go → O(n)

● Height of Heap Tree: log n

● Each insertion may require up to log n swaps/comparisons (in worst case).

4. Summary Table

Method Approach Time Complexity Description

Insertion Insert keys one by one O(n log n) Swap upward after each
insertion

Heapify Place all keys, then O(n) Convert array into heap directly
adjust

🧩 Max Heap (Array Representation & Deletion)

[Link]
v=7gWrUhQxFIU&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=34
1. What is a Max Heap?
● A binary tree where each parent node is greater than or equal to its children.

● Implemented using an array (index-based structure).

● Root node → largest element in the heap.

📘 Properties:

1. Must be an Almost Complete Binary Tree (ACBT).

2. Parent > Child at every level.

3. Array Index Rule:

○ For node at index i:

■ Left child = 2i + 1

■ Right child = 2i + 2
 ■ Parent = (i - 1) / 2

2. Example Question (Gate 2009)

Q: Which array represents a Max Heap?

Options given:
A. [25, 12, 16, 13] ❌ (parent smaller than child)
B. [25, 14, 13, 16] ❌ (violation in Max Heap order)
C. [25, 14, 16, 13, 10, 8, 12] ✅ (correct Max Heap)
D. [25, 14, 12, 13, 10, 8, 16] ❌ (parent smaller than child)

✅ Correct Answer: Option C

📊 Heap Tree for Option C:

25

/ \

14 16

/ \ / \

13 10 8 12

3. Deletion in Max Heap

● Always delete the root (maximum element).

● Replace root with last leaf node.

● Then Heapify (reorder) to restore Max Heap property.

4. Example — Two Delete Operations

Start with correct Max Heap → [25, 14, 16, 13, 10, 8, 12]

🧮 First Deletion
 ● Delete root (25)

● Replace root with last leaf (12) → [12, 14, 16, 13, 10, 8]

● Heapify → [16, 14, 12, 13, 10, 8]

🧮 Second Deletion

● Delete root (16)

● Replace with last leaf (8) → [8, 14, 12, 13, 10]

● Heapify → [14, 13, 12, 8, 10]

✅ Final Array After 2 Deletions: [14, 13, 12, 8, 10]

5. Time Complexities

Operation Description Time Complexity

Insertion Add one element and O(log n)

adjust

Deletion Remove root and heapify O(log n)

Build Heap (one-by-one) Insert elements individually O(n log n)

Build Heap (Heapify) Construct heap directly O(n)

Heap Sort Repeated delete + heapify O(n log n)

✅ Summary
● Max Heap: Parent ≥ Children

● Root: Maximum element

 ● Example (Correct Heap): [25, 14, 16, 13, 10, 8, 12]

● After 2 Deletions: [14, 13, 12, 8, 10]

● Important: Know insertion, deletion, heapify process, and time complexities for
exams/interviews.

🌳 Heapify Method (Heap Construction)

[Link]
v=8noP3YjjJCM&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=35

🔹 What is Heapify?
● Heapify is a method used to build a heap (Max or Min Heap) from an unsorted array.

● It rearranges elements to satisfy the heap property in O(n) time.

● Alternative method: Insert one by one → O(n log n) time.

🔹 Types of Heaps
● Max Heap: Parent ≥ Child

● Min Heap: Parent ≤ Child

🔹 Basic Idea of Heapify

1. Create a complete binary tree from given elements (fill level by level, left to right).
Example array:
40, 25, 65, 12, 48, 18, 1, 100, 27, 7, 3, 45, 9, 30

2. Convert it into a heap (say Min Heap) by rearranging nodes.

3. Start from bottom non-leaf nodes (since leaves already satisfy heap property).

4. Compare parent with children and swap to maintain Min/Max heap property.

5. Repeat up the tree until the entire heap is fixed.

🔹 Important Points
● Leaf nodes: No swapping required.

● Half of the total nodes (≈ n/2) are leaves.

● Non-leaf nodes are heapified.

● Number of swaps per node depends on its height:

○ Bottom level → 0 swaps

○ Above level → 1 swap

○ Next level → 2 swaps

○ Top level → log n swaps

🌳 Heap Deletion (Min Heap Example)

[Link]
v=4GsxDWMI7tQ&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=36

🔹 1. What is Deletion in Heap?

● Deletion means removing an element (key) from a heap tree.

● In heaps, you cannot delete any random element directly because it would break the
Almost Complete Binary Tree (ACBT) structure.

🔹 2. Which Elements Can Be Deleted Directly?

You can directly delete only two types of elements:

1. Root element (top of the heap)

2. Rightmost element at the lowest level

🔹 3. Why Not Delete Others Directly?
● If you delete any middle element (like 2, 3, 4, etc.),
→ the tree will no longer be an ACBT,
→ and heap structure breaks.

🔹 4. Deleting the Rightmost Lowest Element

● Example: Delete 7 (rightmost, lowest).

● Simply remove it — no rearrangement needed.

✅ Time complexity (best case): O(1)

🔹 5. Deleting the Root Element

Example Min Heap:

/ \

2 3

/ \ / \

4 5 6 7

Steps:

1. Remove the root (1).

2. Take the rightmost lowest element (6) and place it at the root.

3. Now check heap property:

○ 6 > 2 → swap (2 becomes root).

○ 6 > 4 → swap again (4 goes up).

✅ Final Heap:

/ \

4 3

/ \ /

6 5 7

🔹 6. Time Complexity

Case Description Time Complexity

Best Case Delete lowest rightmost O(1)

node

Worst Delete root + rearrange heap O(log n)

Case

🔹 7. Comparison: Insertion vs Deletion

Operation Direction Best Worst

Case Case

Insertion Bottom → O(1) O(log n)

Top

Deletion Top → O(1) O(log n)

Bottom

For n elements,
➡ Total = O(n log n)
✅ Summary
● Can delete only root or rightmost lowest element directly.

● If root deleted → replace with rightmost node → heapify downward.

● Best case: O(1), Worst case: O(log n).

● Insertion → bottom-up; Deletion → top-down.

🌳 Heap Sort – Notes

[Link]
v=nJ6FdAIr_6g&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=37

🔹 1. What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that uses a heap data structure to sort
elements.
It can sort data in ascending or descending order depending on the type of heap used.

🔹 2. Prerequisites
Before learning Heap Sort, you must know:

● How to create a heap (insertion / buildHeap)

● How to delete from a heap

🔹 3. Steps in Heap Sort

Step 1 – Build the Heap

● Convert the given array into a heap (Min Heap or Max Heap).

● Use Heapify / BuildHeap method.

● Time complexity: O(n)

Step 2 – Delete Elements One by One

 ● Remove the root element each time (smallest in Min Heap, largest in Max Heap).

● Replace root with the rightmost element at the lowest level.

● Heapify again to maintain heap property.

● Repeat until all elements are deleted and sorted.

● Each deletion: O(log n)

🔹 4. Example (Ascending Order using Min Heap)

Input: 4, 6, 10, 9, 2
Build Min Heap:

/ \

4 10

/ \

9 6

Sorted Output: 2, 4, 6, 9, 10

🔹 5. Time Complexity

Operation Time

Build Heap O(n)

Deletion (n elements × log n) O(n log n)

Total O(n log n) in all cases (Best, Avg,

Worst)
🔹 6. In-Place Sorting
● Heap Sort does not require extra space.
✅ Works within the same array → In-Place algorithm

🔹 7. Stability
● Heap Sort is Unstable.

● Meaning: The relative order of equal elements can change.

Example:
Input → 3A, 3B, 3C
Output → 3C, 3B, 3A (Order changed ❌)

✅ Summary
● Uses heap data structure.

● Build Heap → Delete Root Repeatedly → Sorted Output.

● Time Complexity: O(n log n)

● Space Complexity: O(1)

● In-place: ✔️

● Stable: ❌

🧮 Hashing – Notes
[Link]

🔹 1. What is Hashing?
● A method to store and retrieve data in constant time (O(1)).

● Used in databases and data structures.

● Called a mapping technique because it maps large values → small values using
a hash function.
🔹 2. Importance
● Very important for GATE, NET, PSUs, and university exams.

● Usually 1–2 questions appear in competitive exams.

🔹 3. Key Terms

Term Meaning

Search A unique value used to identify a record (e.g., Roll no., Passport
Key no.)

Hash Table A data structure (array-like) used to store keys.

Index The position in the hash table where data is stored.

🔹 4. Why Hashing?
● No need to scan the entire array.

● Using a hash function, you can find, insert, or delete data in O(1) time.

🔹 5. Hash Function
● Converts a key (K) into an index of the hash table.

● Common functions:

○ K mod N

○ Mid-Square Method

○ Folding Method
🔹 6. Example (K mod N method)

If K = 24 and Hash function = K mod 10

→ 24 mod 10 = 4
→ Store 24 at index 4 in the hash table.

More examples:

Key K mod 10 Index

24 4 4

52 2 2

91 1 1

67 7 7

48 8 8

83 3 3

🔹 7. Operations

Operation Description Time

Insertion Compute hash → place O(1)

key

Search Compute hash → go to O(1)

index

Deletion Search → remove from O(1)

index
🔹 8. Example of Other Hash Functions
● Mid-Square Method: Square the key and use middle digits as index.

● Folding Method: Divide key into parts, add parts, use result as index.

Example:
Key = 123456, Table = 0–999
→ Fold: 123 + 456 = 579 → store at index 579.

🔹 9. Collision
● Happens when two keys get the same index.
Example:
52 mod 10 = 2, 62 mod 10 = 2 → both go to index 2 → collision occurs.

● Collision resolution methods will be discussed separately

💥 Collision Resolution in Hashing – Notes

[Link]
mgCY&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=63
🔹 1. What is Collision?
● A collision happens when two or more keys are mapped to the same index in the
hash table.

● Example:

○ Hash function: K mod 6

○ Keys: 32 and 44

○ Both give remainder 2, so both go to index 2 → collision occurs.

🔹 2. Need for Collision Resolution

● Since hash tables can’t store multiple elements at the same index,
we use collision resolution techniques to handle such cases.
🔹 3. Types of Collision Resolution
There are two main categories:

Type Also Called Description

Open Hashing Chaining Uses extra memory (like linked lists) outside the table

Closed Open Resolves collisions within the same table

Hashing Addressing

🔸 A. Open Hashing (Chaining)

➤ Concept
● Each index of the hash table points to a linked list.

● When a collision occurs, the new key is added to the chain at that index.

Example:
If both 32 and 44 hash to index 2,
then index 2 → [32 → 44]

➤ Why “Open”?
● Because it uses external (extra) space outside the main table.

➤ Advantages
● Simple to implement.

● Table never gets full (you can keep adding to the list).

➤ Disadvantages
● Uses extra memory.
 ● Search time increases if long chains form.

🔸 B. Closed Hashing (Open Addressing)

➤ Concept
● All elements are stored within the table itself (no external memory).

● When a collision happens, the algorithm searches for another empty spot in the table
using a formula.

1. Linear Probing
● Formula:
H(i) = (H(key) + i) mod N

● Check the next available position one by one (sequentially).

Example:
If index 2 is full → check index 3 → 4 → 5 … until an empty spot is found.

Pros: Simple and fast for small data.

Cons: Causes primary clustering (grouping of filled cells).

2. Quadratic Probing
● Formula:
H(i) = (H(key) + i²) mod N

● Check positions by skipping squares: +1², +2², +3² …

Example:
Key = 30, Function = K mod 6

● 30 mod 6 = 0 → index 0 is full

● Try (0 + 1²) mod 6 = 1 → index 1 (if full)

 ● Try (0 + 2²) mod 6 = 4 → index 4 → store there

Pros: Reduces clustering.

Cons: May still skip some empty spots.

3. Double Hashing
● Uses two hash functions:

○ H1(key) → primary hash

○ H2(key) → used if collision occurs

Formula:
H(i) = (H1(key) + i * H2(key)) mod N

Pros: Minimizes clustering effectively.

Cons: Slightly complex and needs two functions

🔗 Chaining in Hashing (Open Hashing) – Notes

[Link]

🔹 1. What is Chaining / Open Hashing?

● Chaining is a collision resolution technique used in hashing.

● When two or more keys map to the same index, a linked list (chain) is created at that
index.

● Each index of the hash table contains a pointer to the head node of a linked list.

● New keys are inserted as nodes in this list.

🔹 2. Example

Hash Function: K mod 5

Keys: 42, 19, 10, 12
Table Indexes: 0 → 4

Key K mod 5 Index Stored at

 42 2 2 [42]

19 4 4 [19]

10 0 0 [10]

12 2 2 [12 → 42] (Chain

formed)

Explanation:

● 42 → index 2

● 12 → also gives index 2 → new node created and linked → 12 → 42

🔹 3. How Chaining Works

● Each slot in the hash table holds a linked list of keys that hash to the same index.

● If a collision occurs, the new key is linked to the existing node.

● Insertion usually happens at the beginning of the chain (like linked list insertion).

🔹 4. Advantages
✅ 1. Easy Deletion:

● Works just like deleting a node from a linked list (adjust pointers).

✅ 2. Simple to Implement:

● Conceptually easy, no complex formula required.

✅ 3. No Need to Resize Table:

 ● Chains can grow dynamically, so the table never becomes “full.”

✅ 4. Works Well with Variable Data:

● Even if hash distribution is uneven, it still functions correctly.

🔹 5. Disadvantages
❌ 1. Extra Memory Required:

● Needs additional space for pointers and linked list nodes.

❌ 2. Slower Search in Worst Case:

● If many keys hash to the same index, a long chain forms → O(n) time.

❌ 3. Poor Cache Performance:

● Linked lists use scattered memory locations, reducing access speed.

🔹 6. Time Complexity

Operation Average Worst

Case Case

Insertion O(1) O(n)

Deletion O(1) O(n)

Searching O(1) O(n)

Worst case occurs when all keys map to the same index, forming one long chain.

🔹 7. Load Factor (α)

 ● Indicates how full the hash table is.

● Formula:
α=Number of elementsNumber of slots\alpha = \frac{\text{Number of elements}}{\
text{Number of slots}}α=Number of slotsNumber of elements
● Example:
4 keys, 5 slots →
α=4/5=0.8\alpha = 4 / 5 = 0.8α=4/5=0.8

🔹 8. Why Called “Open Hashing”?

● Because it uses extra memory outside the main hash table (linked lists).

● Data is stored openly beyond the fixed table size.

💡 Linear Probing – Hashing Notes

[Link]

🔹 1. What is Linear Probing?

Linear probing is a collision resolution technique in open addressing (hashing).
When a collision occurs, the algorithm linearly searches for the next empty slot.

🔹 2. Hash Function Example

If hash function is

h(k) = k mod 10

Then the hash table has indexes from 0 to 9 (since remainder ranges from 0–9).

Example keys: 43, 135, 72, 23, 99, 19, 82

● 43 mod 10 = 3 → index 3

● 135 mod 10 = 5 → index 5

● 72 mod 10 = 2 → index 2
 ● 23 mod 10 = 3 → collision → next empty index (4)

👉 When a collision happens, use:

h(k, i) = (h(k) + i) mod m

where i = probe number (collision count).

🔹 3. Insertion Rule
If the slot is full, move to the next index (i+1).
If you reach the end, wrap around to index 0.
Insert at the first empty slot found.

🔹 4. Probe Number (i)

Number of attempts made to find an empty space.

Example:

● For 72 → found empty on 1st try → i = 1

● For 82 → found empty on 5th try → i = 5

🔹 5. Advantages
✅ No extra space — uses existing hash table (closed hashing).
✅ Easy implementation — simple and sequential probing.
✅ Insertion — constant time on average, O(1).

🔹 6. Disadvantages
❌ Searching time →

● Best case: O(1)

● Worst case: O(n) (if many collisions)

❌ Deletion is difficult — removing an element can break the search sequence.

➡ To fix, use a special marker (e.g. "deleted") so searching continues.
❌ Primary Clustering —
Groups of consecutive filled slots (clusters) form, increasing future collisions.
👉 Probability of collision rises near these clusters.
Example: elements crowding around nearby indices.

❌ Secondary Clustering —
When two or more keys follow the same probe sequence while searching for empty slots.

🔹 7. Complexity

Op A W
era v o
tio e r
n r s
a t
g
e

Ins O O
erti ( (
on 1 n
) )

Se O O
arc ( (
hin 1 n
g ) )

Del O O
eti ( (
on 1 n
) )

🔹 8. Comparison with Chaining

Feature Linear Chaining

Probing
 Type Open Open
Addressi Hashing
ng

Extra Space ❌ No ✅ Yes

(linked
lists)

Deletion Difficult Easy

Clustering Present No clustering

Time Complexity O(n) O(n)

(worst)

✅ Summary
● Collision resolved by checking next slot linearly.

● Uses same table (no extra space).

● Suffers from primary & secondary clustering.

● Deletion tricky.

● Efficient for small load factors.

💡 Hashing – Linear Probing Example (Gate Question)

[Link]
v=go45eeMrwA4&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=66

🔹 Question Statement
Keys are inserted into an empty hash table of length 10 using open addressing.
Hash function used:

h(i) = i² mod 10

Collision is resolved using linear probing.

Tasks:

1. Construct the final hash table

2. Find the maximum probe value

🔹 Given Keys

1, 3, 12, 4, 25, 6, 18, 20, 8

🔹 Step 1: Prepare Hash Table

Length = 10 → Indexes = 0 to 9

🔹 Step 2: Insert Each Key Using h(i) = i² mod 10

Ke i² i² mod Target Collision? Final Probe

y 10 Index Index Count

1 1 1 1 ❌ 1 1

3 9 9 9 ❌ 9 1

12 14 4 4 ❌ 4 1
4

4 16 6 6 ❌ 6 1

25 62 5 5 ❌ 5 1
5

6 36 6 6 ✅ (occupied by 4) 7 2

18 32 4 4 ✅ (occupied by 12) 8 5
4
20 40 0 0 ❌ 0 1
0

8 64 4 4 ✅ (filled) → probe sequentially 3 9

until empty

🔹 Step 3: Final Hash Table

Index Key

0 20

1 1

2 —

3 8

4 12

5 25

6 4

7 6

8 18

9 3

🔹 Step 4: Maximum Probe Value

 ● Maximum probe (number of checks before insertion) = 9

● Occurs for key 8

🧩 Concept Recap
● Collision: When two keys hash to the same index.

● Linear probing rule: Move to next index (index + 1) until an empty slot is found.

● Probe number (i): Number of attempts to find an empty slot.

● Maximum probe: Highest number of attempts among all insertions.

✅ Final Answers
● Resultant Hash Table:
[20, 1, –, 8, 12, 25, 4, 6, 18, 3]

● Maximum Probe Value: 9 (for key 8

🧩 Quadratic Probing – Hashing Notes

[Link]
Jn0A&list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&index=67

🔹 Basic Idea
● Quadratic Probing is a collision resolution technique used in open addressing in
hashing.

● When a collision occurs, instead of checking the next cell (like in linear probing), it
checks positions quadratically away.

🔹 Hash Function
Usually given as:

h(k)=(kmod m)h(k) = (k \mod m)h(k)=(kmodm)

where m is the size of the hash table.

If collision occurs:

hi(k)=(h(k)+i2)mod mh_i(k) = (h(k) + i^2) \mod mhi(k)=(h(k)+i2)modm

where i = 0, 1, 2, 3, ... (number of probes or collision attempts)

🔹 Example

Keys: 42, 16, 91, 33, 18, 27, 36, 62

Table size = 10

Key k mod Insert Position Remarks

10

42 2 2 Empty → 42 placed

16 6 6 Empty → 16 placed

91 1 1 Empty → 91 placed

33 3 3 Empty → 33 placed

18 8 8 Empty → 18 placed

27 7 7 Empty → 27 placed

36 6 Collision at 6 → try (6+1²)=7 (filled) → 36 placed at 0

(6+2²)=10→0

62 2 Collision chain: 3→6→1→8→7 → still no ❌ no empty slot found

space (stuck in loop)

⚙️Working Concept
 ● Starts from the hash index.

● If collision occurs, probe sequence will be:

h(k), (h(k)+12)mod m, (h(k)+22)mod m, (h(k)+32)mod m, and so on.h(k),\; (h(k)+1^2) \
mod m,\; (h(k)+2^2) \mod m,\; (h(k)+3^2) \mod m,\; \text{and so on.}h(k),(h(k)+12)modm,
(h(k)+22)modm,(h(k)+32)modm,and so on.
● Works in a quadratic manner (1², 2², 3², 4²...).

✅ Advantages
● No extra space needed (unlike chaining).

● Primary clustering is reduced compared to linear probing.

○ (Primary clustering = consecutive filled cells forming long groups.)

❌ Disadvantages
● No guarantee of finding an empty slot even if table isn’t full.

○ Some keys may never find a space due to cyclic probing.

● Secondary clustering still occurs.

○ (Two keys with same initial hash follow same probe sequence.)

● Worst-case time complexity: O(n) for insertion/search/deletion.

● Harder to implement than linear probing.

💡 Terminology
● Collision: When two keys hash to the same index.

● Probe sequence: The series of positions checked during collision handling.

● Primary clustering: Large group of consecutive filled slots.

● Secondary clustering: Different keys follow the same probe sequence.

🧩 Double Hashing – Hashing Notes
[Link]
v=1P7ygNSe9lY&list=PLxM5rzx4f4fwOPORqEZZhaaY5OG0WMZfF&index=7

🔹 Basic Concept
● Double Hashing is another open addressing collision resolution method.

● As the name says — it uses two hash functions:

h1(k)andh2(k)h_1(k) \quad \text{and} \quad h_2(k)h1(k)andh2(k)
● When a collision occurs, instead of moving linearly or quadratically, we use a second
hash function to calculate the next position.

🔹 Formula
If the first hash gives a collision:

hi(k)=(h1(k)+i×h2(k))mod mh_i(k) = (h_1(k) + i \times h_2(k)) \mod mhi(k)=(h1(k)+i×h2(k))modm

where:

● h₁(k) = primary hash function

● h₂(k) = secondary hash function

● m = size of the hash table

● i = number of collision attempts (1, 2, 3, ...)

🔹 Example
Keys = {20, 34, 45, 70, 56}
Hash table size (m) = 11

Given functions:

● h₁(k) = k mod 11

● h₂(k) = 8 – (k mod 8)
 Key h₁(k h₂(k Insertion Process Final
) ) Position

20 9 — Empty → placed 9

34 1 — Empty → placed 1

45 1 3 1 filled → (1 + 1×3) % 11 = 4 4

70 4 2 4 filled → (4 + 1×2) % 11 = 6 6

56 1 8 1 filled → (1 + 1×8)=9 (filled) → (1 + 2×8)=17 % 3

11 = 6 (filled) → (1 + 3×8)=25 % 11 = 3

✅ Final Hash Table

Index 0 1 2 3 4 5 6 7 8 9 10

Key — 34 — 56 45 — 70 — — 20 —

⚙️Important Conditions

● h₂(k) must never be 0.

● The hash table size m should be prime.

● h₂(k) and m should be relatively prime (to ensure all slots are probed).

● Ensures uniform distribution of keys.

✅ Advantages
● No extra space required (open addressing method).
 ● Primary clustering removed
(no long chain of filled consecutive slots).

● Secondary clustering removed

(no two keys follow same probe sequence).

● Gives better distribution than linear/quadratic probing.

● Average & best case time: O(1)

❌ Disadvantages
● Complex to compute (two hash functions needed).

● Worst-case time: O(n)

● Need to carefully design h₂(k) so it’s nonzero and relatively prime to table size.

💡 Comparison Summary

Method Formula Clustering Guarantee of Empty

Slot

Linear Probing (h(k) + i) mod m Primary + ✅

Secondary

Quadratic (h(k) + i²) mod m Secondary only ❌

Probing

Double Hashing (h₁(k) + i × h₂(k)) mod None ✅

m

🧠 In Short
● Uses two hash functions for collision resolution.

● Avoids both primary and secondary clustering.

 ● Gives uniform distribution of keys.

● Best and average case: O(1)

● Worst case: O(n)

DIRECT ADDRESS TABELS IN HASHING:

🧩 Question:
We have a set of keys representing employee IDs:

Keys = {0, 2, 5, 7}

Each key stores the employee’s salary.

Create a Direct Address Table (DAT) for these keys and show how the data is stored and
retrieved.

🧮 Step 1: Understand what direct addressing means

In direct addressing,
each key acts as an index in an array.
So we’ll create an array (say A) whose index numbers = key values.

The maximum key here is 7,

so the table size = 8 (from index 0 to 7).

🧱 Step 2: Create the Direct Address Table

Let’s assume the salaries are:

Key (Employee ID) Salary ($)

0 5000

2 7000
 5 6500

7 8000

Now, we store them directly at the index = key.

Index (Key) Stored Data (Salary)

0 5000

1 —

2 7000

3 —

4 —

5 6500

6 —

7 8000

Here, “—” means the slot is empty (no employee with that ID).

⚙️Step 3: Performing operations

✅ Insert(key, value):
Just assign directly:

A[key] = value

Example: A[2] = 7000

✅ Search(key):
Just access directly:

return A[key]

Example: A[5] → 6500

✅ Delete(key):
Just set it to null:

A[key] = null

Step 4: Time Complexity

● Insertion: O(1)

● Search: O(1)

● Deletion: O(1)

(because we go directly to the index — no hashing or collision handling needed!)

⚠️Limitations
If the key values are very large (say IDs are 1000, 5000, 9000),
we’d need an array of size 9001 — which wastes memory.
That’s why we use hashing for large key ranges.

UNIVERSAL HASHING:
Universal Hashing

[Link]

🧠 UNIVERSAL HASHING — Summary Notes

🌍 The Core Problem: The Dictionary Problem
● You have a massive universe of possible items (e.g., all possible usernames).

● But you only care about a small subset (the ones actually in use).

● You need to insert, delete, and search items very fast.

Goal: Achieve fast (constant-time) operations without wasting huge amounts of memory.

⚡ The Classic Trade-off

Method Time Spac Problem

e

Simple list O(n) Small Too slow

Bit vector (direct addressing) O(1) Huge Wastes

space

We want speed like a bit vector but space efficiency like a list → that’s where hashing
comes in.

🔢 Hashing Basics
● A hash function turns a key (like a username) into an array index.

● Example: h(k) = k mod m

● Ideal case: distributes keys evenly across all slots.

● Collision: when two keys hash to the same index.

🔗 Chaining (Collision Handling)

● Each slot stores a linked list (or chain) of keys that hash to that slot.

● If collisions are few, lists stay short → lookup is still very fast.
⚠️The Problem With Fixed Hash Functions
● If your hash function is predictable, an attacker (or bad data) can cause massive
collisions.

● Example: All keys hash to slot 0 → table becomes one long list → time goes
back to O(n).

● Hashing fails if someone can control or predict the hash function.

🎲 The Fix: Randomness → Universal Hashing

Idea: Instead of one fixed hash function, use a family of hash functions and pick one at random
at runtime.

Randomness = unpredictability = protection against worst-case scenarios.

🧮 How Universal Hashing Works

1. Choose a large prime number p.

2. Randomly pick numbers a and b.

3. Define a hash function:

ha,b(k)=((a×k+b)mod p)mod mh_{a,b}(k) = ((a \times k + b) \mod p) \mod mha,b

(k)=((a×k+b)modp)modm

● m: size of hash table

● Each (a, b) pair gives a different hash function.

● Every run → pick a new random (a, b).

This makes it impossible for anyone to predict or force collisions.

📊 Mathematical Guarantee
For any two distinct keys x and y:

P[h(x)=h(y)]≤1mP[h(x) = h(y)] \leq \frac{1}{m}P[h(x)=h(y)]≤m1

→ Collisions are very unlikely.

🚀 Performance
● Expected time per operation: O(1)

● Average chain length: < 2

● Worst case (rare): O(n)

It combines:
✅ Efficient space
✅ Constant average lookup time
✅ Robustness against adversarial inputs

⚙️Advantages
● Prevents deliberate collision attacks.

● Distributes keys uniformly.

● Keeps expected lookup/insertion/deletion time constant.

● Used in cryptography, hash maps, and randomized algorithms.

⚠️Disadvantages

● Slightly more setup (needs random a, b).

● Requires good random number generation.

● Slightly higher constant factor in computation.

🧩 Summary Table

Concept Normal Hashing Universal Hashing

 Hash function Fixed Randomly chosen from a family

Predictability High Unpredictable

Collisions Can be forced Very low probability

Security Weak Strong (resists attacks)

Time (avg) O(1) O(1)

Time (worst) O(n) Still O(n), but extremely unlikely

💬 Final Insight
Universal hashing shows how randomness makes systems stronger.
It’s not chaos — it’s controlled unpredictability.
That idea powers not just hashing, but also modern cryptography, secure networks, and
randomized algorithms — where a little bit of randomness protects us from the worst.

ChatGPT said:

Applications of Priority Queue (Concise):

1. CPU Scheduling – Used to select the next process based on priority.

Use of Priority Queue in Dijkstra’s and Prim’s Algorithms:

● In Dijkstra’s Algorithm (Shortest Path):

The priority queue is used to always pick the vertex with the smallest current distance
from the source.

○ Initially, all vertices are placed in the priority queue with their tentative distances.

○ The algorithm repeatedly removes (dequeues) the vertex with the minimum
distance value (highest priority).

○ Then, it updates the distances of its neighboring vertices and adjusts

their priorities in the queue.
 → This ensures that the shortest path is always found efficiently.

● In Prim’s Algorithm (Minimum Spanning Tree):

The priority queue is used to pick the edge with the minimum weight that connects a
new vertex to the growing tree.

○ Each step extracts the edge with the smallest weight from the priority queue.

○ The new vertex is added to the tree, and all its connecting edges are
pushed into the queue.
→ This helps in efficiently finding the next smallest edge to add,
ensuring an optimal spanning tree.

2. Event-Driven Simulations –Event-Driven Simulations:

In event-driven simulations, a priority queue is used to manage events based on the
time they occur.
Each event is given a priority equal to its scheduled time.
The simulation repeatedly removes the event with the earliest time (highest priority)
from the queue, processes it, and possibly adds new future events.
3. ✅ Example:
In a traffic simulation, car arrivals and departures are stored in a priority queue,
ensuring events are handled in the correct time order.

4. Load Balancing / Bandwidth Management – To prioritize tasks or data packets.

5. Job Scheduling in OS / Print Queue – Higher priority jobs handled first.

That’s a fantastic and very smart
question
That’s a fantastic and very smart question — you’re thinking like a real problem solver 👏

Let’s break this down so you’ll never be confused again about Kruskal’s, Prim’s, Dijkstra’s, or
Knapsack.
We’ll go step by step:
11 What each algorithm is,
1️⃣
2️⃣When to use it,
3️⃣A small real-world example, and
4️⃣How to recognize which one fits your problem.

🧭 1. Kruskal’s Algorithm (Minimum

Spanning Tree)
💡 What it does:
Kruskal’s finds a Minimum Spanning Tree (MST) — a set of edges that connects all vertices of
a graph with the minimum total cost, without cycles.

⚙️When to use it:

● When you’re asked to connect all cities, computers, or nodes with minimum cost.

● Graph is sparse (few edges).

● Edges are given as a list with weights.

Example:
You’re a network engineer connecting 5 offices with cables of different costs between them.
You want all offices connected with minimum total wire cost.

✅ Use Kruskal’s Algorithm to select which cables to lay.

🧩 Input/Output:
Input: Weighted graph (edges with costs)
Output: Set of edges (tree) with minimum total weight connecting all nodes.

⚖️Key Feature:
 ● Works edge by edge.

● Sort edges by weight.

● Add smallest edges that don’t form cycles.

● Time complexity: O(E log E)

🧩 2. Prim’s Algorithm (Minimum Spanning

Tree)
💡 What it does:
Prim’s also finds a Minimum Spanning Tree, but it grows the tree starting from a single
vertex.

⚙️When to use it:

● When you have a dense graph (many edges).

● When you can easily represent it as a matrix.

● When you want to start from one specific node (like a central city).

Example:
You’re an electricity company starting from the power station (node A).
You want to connect all cities with minimum wiring cost.

✅ Use Prim’s Algorithm because you start at one node and expand outward.

⚖️Key Feature:
● Works vertex by vertex (adds nearest neighbor each time).

● Always keeps one connected component.

● Time complexity: O(V²) (or O(E log V) with heaps).

🚗 3. Dijkstra’s Algorithm (Shortest Path)
💡 What it does:
Finds the shortest path from one source node to every other node in a weighted graph
(non-negative weights).

⚙️When to use it:

● When you need to find the shortest or fastest route from a start point.

● Example questions:

○ “What is the shortest path from A to B?”

○ “Find the shortest route from Karachi to all other cities.”

✅ Use Dijkstra’s Algorithm for shortest-path problems (not MST).

Example:
You’re using Google Maps —
It finds the fastest route from your location to all nearby destinations.

⚖️Key Feature:
● Works node by node, expanding the shortest known distance.

● Doesn’t need to visit all nodes unless required.

● Time complexity: O(V²) or O(E log V) with priority queue.

🎒 4. Knapsack Problem (Optimization /

Dynamic Programming)
💡 What it does:
Given items with weights and values, and a bag of limited capacity,
choose items to maximize total value without exceeding weight.

⚙️When to use it:

 ● When you must choose the best combination of items/resources under a constraint
(limit).

✅ Use Knapsack for selection/optimization problems, not graphs.

Example:
You’re a thief with a bag that can carry 10kg.
Items:

● Gold (6kg, ₹30)

● Silver (3kg, ₹14)

● Bronze (4kg, ₹16)

You want to pick the combination with maximum value ≤ 10kg.

⚖️Key Feature:
● 0/1 Knapsack → take or skip item

● Fractional Knapsack → can take part of an item (greedy)

● Time complexity: O(n * W) for 0/1 (using DP).

🔍 How to Decide Which Algorithm to Use

Situation / Problem Statement Best Algorithm Why

“Connect all cities with minimum cost” Kruskal’s / Prim’s MST problem (connectivity +
min cost, no cycles)

“Find the shortest route from Karachi to Dijkstra’s Shortest path from one node
Lahore” to another

“Find the shortest routes from Karachi Dijkstra’s Single-source shortest paths
to all cities”

“Select best combination under Knapsack Optimization with constraints

weight/budget limit”

“Build a network where everyone is Prim’s or MST problem

 connected minimally” Kruskal’s
“Plan the fastest delivery route visiting Travelling Cycle visiting all nodes exactly
each city once and returning” Salesman (TSP) once

“Find cheapest Internet cable layout” Kruskal’s MST edge-based selection

“You start at one node and expand Prim’s MST vertex-based expansion
connections outward”

🧩 Simple Visual Summary

Algorith Type Works Approach Result
m On

Kruskal’s Graph (MST) Edges Greedy (sort edges) Min total cost
connecting all

Prim’s Graph (MST) Vertices Greedy (expand from Min total cost
one node) connecting all

Dijkstra’s Graph (Shortest Vertices Greedy (shortest path Shortest path

Path) tree) distances

Knapsac Optimization Items Dynamic Programming / Maximize value

k Greedy under limit

🧠 Quick Tip for Exams

When reading a question:

1. See if there’s a graph.

○ If it says “connect all nodes” → MST (Kruskal/Prim).

○ If it says “shortest path” → Dijkstra.

2. If there’s capacity/weight/value → Knapsack.

3. If it says ‘visit each city once and return’ → TSP.

Would you like me to make a visual chart / flow diagram comparing all four (Kruskal, Prim,
Dijkstra, Knapsack) — so you can memorize it for exams easily?

You said:

Dynamic Programming / Greedy

is 0/1 dynamic or greedy?

ChatGPT said:

Excellent question — and it’s one that often confuses people at first 👏

Let’s clear this up once and for all 👇

🎒 Knapsack comes in two main types:

Type Description Approach Example

0/1 You can either take an item ✅ Dynamic “You can either take the
Knapsack (1) or leave it (0). No Programming laptop or leave it — can’t
fractions allowed. take half.”

Fractional You can take a fraction of ✅ Greedy “You can take half the
Knapsack an item. Algorithm gold bar.”

🔹 Why 0/1 Knapsack is Dynamic Programming (DP)

Because:

● You must decide optimally between two choices for each item:

○ Take it (and reduce capacity)

○ Leave it (keep capacity)

● You solve overlapping subproblems, e.g.:

Best value for 5kg using first 3 items depends on solutions for smaller subproblems (like
4kg or 2 items).

● You store results in a table (DP array) to avoid recalculating.

🧠 DP Recurrence Relation:
dp[i][w]=max⁡(dp[i−1][w],value[i]+dp[i−1][w−weight[i]])dp[i][w] = \max(dp[i-1][w],
\text{value}[i] + dp[i-1][w - \text{weight}[i]])dp[i][w]=max(dp[i−1][w],value[i]
+dp[i−1][w−weight[i]])

● if weight[i] ≤ w

● else dp[i][w] = dp[i-1][w]

So it’s clearly a Dynamic Programming problem, not Greedy.

🔹 Why Fractional Knapsack is Greedy

Because:

● You sort items by value/weight ratio.

● Pick the highest ratio first until the bag is full.

● It’s locally optimal at each step — and this works perfectly for fractional cases.

✅ Summary Table
Knapsack Type Approach Reason

0/1 Knapsack Dynamic Must explore combinations; greedy fails

Programming

Fractional Greedy Algorithm Local optimal = global optimal (fractions

Knapsack allowed)

⚠️Quick Check:
If you can’t cut items (0 or 1 only) → Dynamic Programming
If you can take fractions → Greedy

Summary Table
Algorithm Stable Reason
?
 1. Quick Sort ❌ Swaps non-adjacent elements

2. Merge Sort ✅ Maintains order during merge

3. Bubble Sort ✅ Swaps adjacent elements only

4. Insertion Sort ✅ Preserves order of equals

5. Selection ❌ Swaps can break order

Sort
6. Heap Sort ❌ Heap reordering breaks
stability
7. Counting Sort ✅ Preserves input order of equals

🧠 1. Memoization (Top-Down Approach)

Definition:
Memoization means storing the results of expensive function calls so that when the same
inputs occur again, you don’t recompute them — you just reuse the stored result.

It’s like saying:

“If I’ve already solved this problem before, I’ll just look up the answer instead of
solving it again!”

Type:
✅ Top-down (uses recursion + caching)

Example:
Let’s take the Fibonacci series example.

👉 Fibonacci formula:
F(n) = F(n-1) + F(n-2)

Without memoization, it re-computes many same values again and again.

Memoization version:

def fib(n, memo={}):

if n <= 1:
return n
if n in memo: # if already calculated, use it
return memo[n]
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
💡 Here, we store the result of fib(n) in a dictionary called memo so we don’t calculate it again.

📋 2. Tabulation (Bottom-Up Approach)

Definition:
Tabulation means solving problems from the bottom up, by building a table (usually an
array) that stores results of subproblems — starting from the base case and moving upward.

It’s like saying:

“I’ll start solving the smallest problems first, store their answers, and use them to
build up to the big problem.”

Type:
✅ Bottom-up (uses iteration + table)

Example:
Fibonacci using tabulation:

def fib(n):
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

💡 Here, dp[i] stores the Fibonacci value for i, and we fill the table step by step.

⚖️Difference Summary
Feature Memoization Tabulation

Approach Top-Down Bottom-Up

Uses Recursion + Cache Iteration + Table

Order Solves bigger problems first (breaks Solves smaller problems first (builds
down) up)

Space Often uses call stack Uses table/array

In short:
🧠 Memoization = “Remember results from recursion.”
📋 Tabulation = “Build results iteratively in a table.”
Tab 3
Summary Table
Algorithm Stable? Reason

1. Quick Sort ❌ Swaps non-adjacent elements

2. Merge Sort ✅ Maintains order during merge

3. Bubble Sort ✅ Swaps adjacent elements only

4. Insertion Sort ✅ Preserves order of equals

5. Selection Sort ❌ Swaps can break order

6. Heap Sort ❌ Heap reordering breaks stability

7. Counting Sort ✅ Preserves input order of equals

Complexities
1. Bubble Sort
Case Time Complexity Explanation

Best O(n) When the array is already sorted (only one pass
needed).
Average O(n²) Every element is compared multiple times.

Worst O(n²) Completely reversed order requires full passes.

Space O(1) In-place sorting (only swaps).

2. Insertion Sort
Case Time Complexity Explanation

Best O(n) Already sorted array, only 1 comparison per element.

Average O(n²) Roughly half of the array needs shifting per insert.

Worst O(n²) Reversed array, maximum shifts per insertion.

Space O(1) In-place algorithm.

3. Selection Sort
Case Time Complexity Explanation

Best O(n²) Always scans the rest of array for the smallest element.

Average O(n²) Same number of comparisons regardless of order.

Worst O(n²) Same — it doesn’t depend on order.

Space O(1) In-place sorting.

4. Merge Sort
Case Time Complexity Explanation

Best O(n log n) Divide & conquer always splits evenly.

Average O(n log n) Each level of recursion merges n elements.

Worst O(n log n) Same process regardless of initial order.

Space O(n) Needs extra arrays during merging.

5. Quick Sort
Case Time Complexity Explanation

Best O(n log n) Balanced partitions each time.

Average O(n log n) Typically balanced partitions.

Worst O(n²) Worst pivot selection (e.g., always smallest/largest).

Space O(log n) Recursive stack (depends on partition depth).

6. Heap Sort
Case Time Complexity Explanation

Best O(n log n) Building heap + extraction.

Average O(n log n) Heapify maintains log n per delete-max.

Worst O(n log n) Same — heap structure guarantees log n per operation.

Space O(1) In-place (heap stored in same array).

Quick Summary Table

Algorithm Best Average Worst Space

Bubble Sort O(n) O(n²) O(n²) O(1)

Insertion Sort O(n) O(n²) O(n²) O(1)

Selection Sort O(n²) O(n²) O(n²) O(1)

Merge Sort O(n log n) O(n log n) O(n log n) O(n)

Quick Sort O(n log n) O(n log n) O(n²) O(log n)

Heap Sort O(n log n) O(n log n) O(n log n) O(1)

Dijsktra: O(E log V)
Stable and unstable
Algorithm Stable? Reason

1. Quick Sort ❌ Swaps non-adjacent elements

2. Merge Sort ✅ Maintains order during merge

3. Bubble Sort ✅ Swaps adjacent elements only

4. Insertion Sort ✅ Preserves order of equals

5. Selection Sort ❌ Swaps can break order

6. Heap Sort ❌ Heap reordering breaks stability

7. Counting Sort ✅ Preserves input order of equals