Design and Analysis of Algorithms

Course Lecture Notes

Overview: These notes cover three fundamental topics in algorithm design: the process of
analyzing algorithms, understanding asymptotic complexity, and the advanced data structure
known as the Binomial Heap.

1. Analyzing Algorithm

1.1 Introduction
Algorithm Analysis is the process of estimating the amount of computational resources
(time and storage) required for an algorithm to execute. The primary goal is to predict
the performance of an algorithm and compare different algorithms for the same
problem to choose the most efficient one.

1.2 Types of Analysis

Analysis can be categorized into two phases:

1. Priori Analysis (Theoretical):

Performed before implementation.
Uses asymptotic notations to express complexity as a function of input size (n).
Independent of hardware, operating system, or compiler.

2. Posteriori Analysis (Empirical):

Performed after implementation.
Involves running the algorithm on a specific machine and measuring actual
time (seconds) and space (bytes).
Dependent on hardware and system configuration.

1.3 Time and Space Complexity

Time Complexity: The amount of time (or number of primitive operations) an

algorithm takes to run as a function of the length of the input.

Space Complexity: The amount of memory space required by the algorithm in its
life cycle. It includes:
 Fixed Part: Space for constants, simple variables, fixed-size variables.
Variable Part: Space for dynamic allocation, recursion stack space.

1.4 Methods of Analysis (Cases)

Since an algorithm's running time may vary depending on the structure of the input, we
analyze three cases:

Case Description Significance

Input is arranged such that Lower bound on performance. Often represented by Ω

Best Case
execution time is minimum. (Omega).

Average Expected execution time averaged Most practical measure but hardest to calculate
Case over all possible inputs. mathematically.

Worst Input is arranged such that Upper bound on performance. Guarantee that the algorithm
Case execution time is maximum. will never take longer than this. Represented by O (Big-O).

1.5 Example 1: Analysis of Linear Search

Problem: Find element x in an array A of size n.

Algorithm:

Algorithm LinearSearch(A, n, x)
Input: Array A of size n, element x to search
Output: Index of x if found, -1 otherwise

Begin
for i = 0 to n-1 do
if A[i] == x then
return i
end if
end for
return -1
End

Complete Implementation (C++):

int linearSearch(int arr[], int n, int x) {

for (int i = 0; i < n; i++) { // n iterations
if (arr[i] == x) { // 1 comparison per iteration
return i; // 1 operation
}
}
return -1; // 1 operation
}

// Example usage:
int main() {
int arr[] = {10, 23, 45, 70, 11, 15};
int n = 6;
int x = 70;

int result = linearSearch(arr, n, x);

if (result != -1)
cout << "Element found at index: " << result;
 else
cout << "Element not found";

return 0;
}

Step-by-Step Analysis:

Best Case Analysis:

Element x is at the first index (A[0]).

Loop executes: 1 time

Comparisons: 1
Total operations: Constant
Time Complexity: Ω(1)

Example: A = [70, 23, 45, 10], x = 70

i=0: A[0]==70 ✓ → return 0 (Found immediately!)

Worst Case Analysis:

Element x is at the last index or not present at all.

Loop executes: n times

Comparisons: n
Total operations: c × n (where c is constant)
Time Complexity: O(n)

Example: A = [10, 23, 45, 70], x = 70

i=0: A[0]==70? No
i=1: A[1]==70? No
i=2: A[2]==70? No
i=3: A[3]==70? Yes → return 3

Average Case Analysis:

Assuming x can be at any position with equal probability 1/n.

If element at position 1: 1 comparison

If element at position 2: 2 comparisons
If element at position n: n comparisons
Average = (1 + 2 + 3 + ... + n) / n
Average = (n(n+1)/2) / n = (n+1)/2 ≈ n/2
Time Complexity: Θ(n)

1.6 Example 2: Analysis of Binary Search

Problem: Find element x in a sorted array A of size n.
Algorithm:

Algorithm BinarySearch(A, left, right, x)

Input: Sorted array A, indices left and right, element x
Output: Index of x if found, -1 otherwise

Begin
if right >= left then
mid = left + (right - left) / 2

if A[mid] == x then
return mid

if A[mid] > x then

return BinarySearch(A, left, mid-1, x)

return BinarySearch(A, mid+1, right, x)

end if

return -1
End

Complete Implementation (C++):

// Recursive Implementation
int binarySearch(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;

// If element is present at middle

if (arr[mid] == x)
return mid;

// If element is smaller than mid, search left half

if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);

// Else search right half

return binarySearch(arr, mid + 1, right, x);
}

// Element not present

return -1;
}

// Iterative Implementation
int binarySearchIterative(int arr[], int n, int x) {
int left = 0, right = n - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}

return -1;
}

Step-by-Step Example:

Array: A = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]
Search for: x = 23
 Iteration 1:
left = 0, right = 10, mid = 5
A[5] = 23
23 == 23? Yes! → Found at index 5

Another Example - Search for: x = 56

Iteration 1:
left = 0, right = 10, mid = 5
A[5] = 23
56 > 23? Yes → Search right half

Iteration 2:
left = 6, right = 10, mid = 8
A[8] = 56
56 == 56? Yes! → Found at index 8

Time Complexity Analysis:

Best Case: Element found at middle → O(1)

Worst Case: Element at leaf or not present
Each iteration divides array by 2
n → n/2 → n/4 → n/8 → ... → 1
Number of iterations k: n/2k = 1 → 2k = n → k = log₂(n)
Time Complexity: O(log n)

Space Complexity:
Recursive: O(log n) - recursion stack
Iterative: O(1) - constant space

1.7 Example 3: Analysis of Bubble Sort

Algorithm:

Algorithm BubbleSort(A, n)
Input: Array A of size n
Output: Sorted array A

Begin
for i = 0 to n-1 do
for j = 0 to n-i-2 do
if A[j] > A[j+1] then
swap(A[j], A[j+1])
end if
end for
end for
End

Complete Implementation (C++):

void bubbleSort(int arr[], int n) {

for (int i = 0; i < n - 1; i++) { // Outer loop: n-1 passes
bool swapped = false;

for (int j = 0; j < n - i - 1; j++) { // Inner loop: comparisons

if (arr[j] > arr[j + 1]) {
// Swap elements
int temp = arr[j];
 arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}

// Optimization: if no swap occurred, array is sorted

if (!swapped)
break;
}
}

Step-by-Step Example:

Initial Array: [64, 34, 25, 12, 22, 11, 90]

Pass 1: (i=0, compare n-1 pairs)

64 34 → 34 64 25 12 22 11 90 (swap)
34 64 25 → 34 25 64 12 22 11 90 (swap)
34 25 64 12 → 34 25 12 64 22 11 90 (swap)
34 25 12 64 22 → 34 25 12 22 64 11 90 (swap)
34 25 12 22 64 11 → 34 25 12 22 11 64 90 (swap)
34 25 12 22 11 64 90 → 34 25 12 22 11 64 90 (no swap)
Result: [34, 25, 12, 22, 11, 64, 90] (90 in place)

Pass 2: (i=1, compare n-2 pairs)

34 25 → 25 34 12 22 11 64 90 (swap)
25 34 12 → 25 12 34 22 11 64 90 (swap)
25 12 34 22 → 25 12 22 34 11 64 90 (swap)
25 12 22 34 11 → 25 12 22 11 34 64 90 (swap)
25 12 22 11 34 64 → 25 12 22 11 34 64 90 (no swap)
Result: [25, 12, 22, 11, 34, 64, 90] (64 in place)

Pass 3, 4, 5, 6... Continue until sorted

Final: [11, 12, 22, 25, 34, 64, 90]

Complexity Analysis:

Best Case: Array already sorted

Only one pass needed (with optimization)
Comparisons: n-1
Time Complexity: Ω(n)

Worst Case: Array sorted in reverse order

Pass 1: (n-1) comparisons
Pass 2: (n-2) comparisons
...
Pass n-1: 1 comparison
Total = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = n²/2 - n/2
Time Complexity: O(n²)

Space Complexity: O(1) - In-place sorting

2. Complexity of an Algorithm
2.1 Asymptotic Notations
Asymptotic notations are mathematical tools to represent the time complexity of
algorithms for asymptotic analysis (when input size n becomes very large).

1. Big O Notation (O) - Upper Bound

Used to describe the worst-case scenario. It bounds a function from above.

f(n) = O(g(n)) if there exist positive constants c and n0 such that:

0 ≤ f(n) ≤ c · g(n) for all n ≥ n0

2. Big Omega Notation (Ω) - Lower Bound

Used to describe the best-case scenario. It bounds a function from below.

f(n) = Ω(g(n)) if there exist positive constants c and n0 such that:

0 ≤ c · g(n) ≤ f(n) for all n ≥ n0

3. Big Theta Notation (Θ) - Tight Bound

Used when the algorithm runs in the same order of growth for best and worst cases. It
bounds a function from above and below.

f(n) = Θ(g(n)) if there exist constants c1, c2 and n0 such that:

0 ≤ c1 · g(n) ≤ f(n) ≤ c2 · g(n) for all n ≥ n0

2.2 Complexity Classes & Growth Rates

Arranged from most efficient (slowest growth) to least efficient (fastest growth):

Class Name Notation Example Algorithms

Constant O(1) Accessing array index, stack push/pop

Logarithmic O(log n) Binary Search

Linear O(n) Linear Search, Tree Traversal

Linearithmic O(n log n) Merge Sort, Heap Sort, Quick Sort

Quadratic O(n2) Bubble Sort, Insertion Sort, Selection Sort

Cubic O(n3) Matrix Multiplication (Naive)

Exponential O(2n) Tower of Hanoi, Travelling Salesman (Brute force)

Growth Comparison Rule:

1 < log n < √n < n < n log n < n2 < n3 < 2n < n!

2.3 Little o and Little omega Notations

4. Little o Notation (o) - Strict Upper Bound

Used to denote an upper bound that is not asymptotically tight. f(n) grows strictly
slower than g(n).

f(n) = o(g(n)) if for any positive constant c, there exists n0 such that:
0 ≤ f(n) < c · g(n) for all n ≥ n0

Example: 2n = o(n²) but 2n² ≠ o(n²)

5. Little omega Notation (ω) - Strict Lower Bound

Used to denote a lower bound that is not asymptotically tight. f(n) grows strictly faster
than g(n).

f(n) = ω(g(n)) if for any positive constant c, there exists n0 such that:
0 ≤ c · g(n) < f(n) for all n ≥ n0

Example: n² = ω(n) but n² ≠ ω(n²)

2.4 Practical Examples of Complexity Analysis

Example 1: Simple Loop

for (int i = 0; i < n; i++) {

cout << i;
}

Analysis:
- Loop runs n times
- Each iteration: O(1)
- Total: O(n)

Example 2: Nested Loops

for (int i = 0; i < n; i++) { // n times

for (int j = 0; j < n; j++) { // n times for each i
cout << i << " " << j;
}
}

Analysis:
- Outer loop: n iterations
- Inner loop: n iterations per outer iteration
- Total operations: n × n = n²
- Time Complexity: O(n²)

Example 3: Dependent Nested Loops

for (int i = 0; i < n; i++) { // n times

for (int j = 0; j < i; j++) { // 0,1,2,...,n-1 times
cout << i << " " << j;
}
}

Analysis:
- i=0: inner loop runs 0 times
- i=1: inner loop runs 1 time
- i=2: inner loop runs 2 times
- ...
 - i=n-1: inner loop runs (n-1) times
- Total: 0+1+2+...+(n-1) = n(n-1)/2 = (n²-n)/2
- Dropping constants and lower order terms: O(n²)

Example 4: Logarithmic Complexity

for (int i = 1; i < n; i = i * 2) {

cout << i;
}

Analysis:
- i starts at 1
- Each iteration: i doubles (1 → 2 → 4 → 8 → 16 → ...)
- Loop stops when i >= n
- Iterations: 1, 2, 4, 8, ..., 2^k = n
- Number of iterations k = log₂(n)
- Time Complexity: O(log n)

Example 5: Logarithmic Loop (Division)

for (int i = n; i >= 1; i = i / 2) {

cout << i;
}

Analysis:
- i starts at n
- Each iteration: i halves (n → n/2 → n/4 → ... → 1)
- n/2^k = 1 → 2^k = n → k = log₂(n)
- Time Complexity: O(log n)

Example 6: Complex Nested Loops

for (int i = 0; i < n; i++) { // n times

for (int j = 0; j < n; j += i) { // varies
cout << i << " " << j;
}
}

Analysis:
- When i=0: infinite loop (avoid this!)
- When i=1: inner loop runs n times
- When i=2: inner loop runs n/2 times
- When i=3: inner loop runs n/3 times
- Total ≈ n + n/2 + n/3 + ... + 1 = n(1 + 1/2 + 1/3 + ... + 1/n)
- This is Harmonic Series ≈ n log n
- Time Complexity: O(n log n)

Example 7: Multiple Consecutive Loops

// Loop 1
for (int i = 0; i < n; i++) {
cout << i;
}

// Loop 2
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
cout << j << " " << k;
}
}

// Loop 3
for (int m = 0; m < n; m++) {
cout << m;
}
 Analysis:
- Loop 1: O(n)
- Loop 2: O(n²)
- Loop 3: O(n)
- Total: O(n) + O(n²) + O(n) = O(n²)
- (Highest order term dominates)

Example 8: If-Else Statement

if (condition) {
// Block A: O(n)
for (int i = 0; i < n; i++) {
cout << i;
}
} else {
// Block B: O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << i << j;
}
}
}

Analysis:
- Checking condition: O(1)
- Block A: O(n)
- Block B: O(n²)
- Worst Case: max(O(n), O(n²)) = O(n²)
- Time Complexity: O(n²)

2.5 Rules for Calculating Complexity

1. Loops: The running time of a loop is the running time of the statements inside the
loop multiplied by the number of iterations.
2. Nested Loops: Analyze inside out. Total time is the product of the sizes of all the
loops.
3. Consecutive Statements: Add the time complexities of each statement.
4. If-Else: Worst-case running time: test time + max(time of "then" part, time of
"else" part).
5. Logarithmic Complexity: Occurs when the problem size is cut by a fraction (e.g.,
halved) in each iteration (like Binary Search).
6. Drop Constants: O(2n) = O(n), O(3n²) = O(n²)
7. Drop Lower Order Terms: O(n² + n) = O(n²), O(n³ + n² + n) = O(n³)

2.6 Recurrence Relations

Many algorithms are recursive, and their time complexity is expressed using recurrence
relations.

Example 1: Binary Search Recurrence

T(n) = T(n/2) + O(1)

Where:
- T(n/2): time for recursive call on half the array
- O(1): constant time for comparison and calculation
 Solution using Master Theorem:
T(n) = O(log n)

Example 2: Merge Sort Recurrence

T(n) = 2T(n/2) + O(n)

Where:
- 2T(n/2): time for two recursive calls on halves
- O(n): time to merge two halves

Solution:
T(n) = O(n log n)

Example 3: Factorial Calculation

int factorial(int n) {
if (n <= 1)
return 1;
return n * factorial(n - 1);
}

Recurrence:
T(n) = T(n-1) + O(1)
T(1) = O(1)

Solution:
T(n) = O(n)

3. Binomial Heap

3.1 Introduction and Definition

A Binomial Heap is a specific type of data structure implemented as a collection of
Binomial Trees. It is a priority queue data structure that supports quicker merging of
two heaps compared to a binary heap.

Key Advantage: While Binary Heaps support Union in O(n), Binomial Heaps support Union in
O(log n).

3.2 Binomial Trees (Bk)

A Binomial Tree of order k, denoted as Bk, is defined recursively:

B0: A single node.

Bk: Consists of two binomial trees of order Bk-1 linked together: the root of one
becomes the leftmost child of the root of the other.

Properties of Bk:

1. Number of nodes = 2k.

2. Height of the tree = k.
3. There are exactly kCi (binomial coefficient) nodes at depth i.
4. The root has degree k (maximum degree in the tree).
3.3 Structure of Binomial Heap
A Binomial Heap H is a set of binomial trees that satisfies two properties:

1. Heap Property: Each binomial tree in H obeys the Min-Heap property (the key of
a node is greater than or equal to the key of its parent).
2. Unique Order Property: There is at most one binomial tree of any given degree k.
(Similar to binary representation of a number).

3.4 Operations and Time Complexity

Time
Operation Description
Complexity

Make-Heap Creates an empty heap. O(1)

Insert(x) Creates a new B0 heap with node x and performs Union. O(log n)

Minimum() Finds the node with the minimum key. (Scan roots of all trees). O(log n)

Removes the node with the minimum key. Includes finding min,
Extract-Min() O(log n)
removing root, and Union of children.

Union(H1,
Merges two binomial heaps. Similar to binary addition. O(log n)
H2)

Decrease-Key Decreases value of a key and bubbles it up if necessary. O(log n)

Delete(x) Decrease key of x to -∞, then Extract-Min. O(log n)

3.5 Detailed Operations on Binomial Heap

3.5.1 Make-Heap Operation

Algorithm Make-Binomial-Heap()
Begin
H = empty heap
return H
End

Time Complexity: O(1)

3.5.2 Insert Operation

To insert a node with key k:

1. Create a new binomial heap H' with a single node (B₀ tree)
2. Perform Union(H, H')

Algorithm Insert(H, k)
Input: Binomial Heap H, key k
Output: Updated heap H with key k inserted

Begin
H' = Make-Binomial-Heap()
 Create node x with key k
Add x to H'
H = Union(H, H')
return H
End

Time Complexity: O(log n)

Complete C++ Implementation:

struct Node {
int key;
int degree;
Node* parent;
Node* child;
Node* sibling;

Node(int k) {
key = k;
degree = 0;
parent = child = sibling = NULL;
}
};

class BinomialHeap {
private:
Node* head; // Pointer to the first root

public:
BinomialHeap() {
head = NULL;
}

// Insert a new key

void insert(int key) {
Node* node = new Node(key);
BinomialHeap* tempHeap = new BinomialHeap();
tempHeap->head = node;
head = unionHeap(head, tempHeap->head);
}

// Link two binomial trees of same degree

Node* mergeTrees(Node* b1, Node* b2) {
// Make sure b1 has smaller key (min-heap property)
if (b1->key > b2->key)
swap(b1, b2);

// Make b2 a child of b1
b2->parent = b1;
b2->sibling = b1->child;
b1->child = b2;
b1->degree++;

return b1;
}

// Union of two binomial heaps

Node* unionHeap(Node* h1, Node* h2) {
if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;

Node* head = merge(h1, h2);

if (head == NULL)
return NULL;

Node* prev = NULL;

Node* curr = head;
Node* next = curr->sibling;

while (next != NULL) {

 // Case 1: degrees are different
if (curr->degree != next->degree ||
(next->sibling != NULL &&
next->sibling->degree == curr->degree)) {
prev = curr;
curr = next;
}
// Case 2: merge curr and next
else {
if (curr->key <= next->key) {
curr->sibling = next->sibling;
mergeTrees(curr, next);
} else {
if (prev == NULL)
head = next;
else
prev->sibling = next;
mergeTrees(next, curr);
curr = next;
}
}
next = curr->sibling;
}

return head;
}

// Merge two binomial heaps (just concatenate)

Node* merge(Node* h1, Node* h2) {
if (h1 == NULL)
return h2;
if (h2 == NULL)
return h1;

Node* head;
if (h1->degree <= h2->degree) {
head = h1;
h1 = h1->sibling;
} else {
head = h2;
h2 = h2->sibling;
}

Node* tail = head;

while (h1 != NULL && h2 != NULL) {

if (h1->degree <= h2->degree) {
tail->sibling = h1;
h1 = h1->sibling;
} else {
tail->sibling = h2;
h2 = h2->sibling;
}
tail = tail->sibling;
}

if (h1 != NULL)
tail->sibling = h1;
else
tail->sibling = h2;

return head;
}
};

3.5.3 Find Minimum Operation

Scan through all root nodes and find the one with minimum key.

Algorithm Find-Minimum(H)
Input: Binomial Heap H
Output: Node with minimum key
 Begin
y = NULL
x = [Link]
min = ∞

while x != NULL do
if [Link] < min then
min = [Link]
y = x
end if
x = [Link]
end while

return y
End

Time Complexity: O(log n)

(At most log n + 1 roots in a binomial heap)

C++ Implementation:

Node* getMin() {
if (head == NULL)
return NULL;

Node* minNode = head;

Node* curr = head->sibling;

while (curr != NULL) {

if (curr->key < minNode->key)
minNode = curr;
curr = curr->sibling;
}

return minNode;
}

3.5.4 Extract-Min Operation

This is the most complex operation:

1. Find the minimum node (let's call it x)

2. Remove x from the root list
3. Reverse the order of x's children and make them a new binomial heap H'
4. Perform Union(H, H')

Algorithm Extract-Min(H)
Input: Binomial Heap H
Output: Minimum key value

Begin
// Find minimum node
x = Find-Minimum(H)

// Remove x from root list

Remove x from [Link] list

// Create new heap H' from children of x

H' = empty heap
Reverse the linked list of x's children
H'.head = reversed children list

// Union the two heaps

H = Union(H, H')
 return [Link]
End

Time Complexity: O(log n)

C++ Implementation:

int extractMin() {
if (head == NULL)
return -1;

// Find minimum and its previous node

Node* minNode = head;
Node* minPrev = NULL;
Node* prev = NULL;
Node* curr = head;
int minKey = head->key;

while (curr->sibling != NULL) {

if (curr->sibling->key < minKey) {
minKey = curr->sibling->key;
minPrev = curr;
minNode = curr->sibling;
}
curr = curr->sibling;
}

// Remove minNode from root list

if (minPrev == NULL)
head = minNode->sibling;
else
minPrev->sibling = minNode->sibling;

// Reverse children of minNode

Node* newHead = NULL;
Node* child = minNode->child;
while (child != NULL) {
Node* next = child->sibling;
child->sibling = newHead;
child->parent = NULL;
newHead = child;
child = next;
}

// Union with reversed children

head = unionHeap(head, newHead);

delete minNode;
return minKey;
}

3.5.5 Decrease-Key Operation

Decrease the key of a node and bubble it up to maintain heap property.

Algorithm Decrease-Key(H, x, k)
Input: Heap H, node x, new key k (k < [Link])
Output: Updated heap

Begin
if k > [Link] then
error "New key is greater than current key"
end if

[Link] = k
y = x
z = [Link]

// Bubble up until heap property is satisfied

while z != NULL and [Link] < [Link] do
 swap([Link], [Link])
y = z
z = [Link]
end while
End

Time Complexity: O(log n)

C++ Implementation:

void decreaseKey(Node* node, int newKey) {

if (newKey > node->key) {
cout << "New key is greater than current key";
return;
}

node->key = newKey;
Node* curr = node;
Node* parent = curr->parent;

// Bubble up
while (parent != NULL && curr->key < parent->key) {
// Swap keys
swap(curr->key, parent->key);
curr = parent;
parent = curr->parent;
}
}

3.5.6 Delete Operation

Delete a node by decreasing its key to -∞ and then extracting minimum.

Algorithm Delete(H, x)
Input: Heap H, node x to delete
Output: Updated heap

Begin
Decrease-Key(H, x, -∞)
Extract-Min(H)
End

Time Complexity: O(log n)

C++ Implementation:

void deleteNode(Node* node) {

decreaseKey(node, INT_MIN);
extractMin();
}

3.6 Step-by-Step Example: Building a Binomial Heap

Insert keys in order: 12, 7, 25, 15, 28, 33, 41

Step 1: Insert 12
H = B₀
12

Step 2: Insert 7
Create B₀ with 7, then Union
B₀(7) and B₀(12) merge to form B₁
7
/
 12

Step 3: Insert 25
Create B₀ with 25, then Union
H now has: B₁ and B₀
7 25
/
12

Step 4: Insert 15
Create B₀ with 15, then Union
B₀(25) and B₀(15) merge to form B₁
Then B₁(7,12) and B₁(15,25) merge to form B₂
7
/|\
12 15
|
25

Step 5: Insert 28
Create B₀ with 28
H now has: B₂ and B₀
7 28
/|\
12 15
|
25

Step 6: Insert 33
Create B₀ with 33, merge with B₀(28) to form B₁
7 28
/|\ /
12 15 33
|
25

Step 7: Insert 41
Create B₀ with 41
All trees merge to form B₃
7
/ | \
12 28 15
| |
33 25
|
41

Final Binomial Heap with 7 nodes = B₀ + B₁ + B₂ = 1 + 2 + 4

Binary: 7 = 111₂

3.7 Extract-Min Example

Starting with heap from previous example, extract minimum (7):

Step 1: Find and remove minimum (7)

Children of 7: [12, 28, 15] (degrees 0, 1, 2)

Step 2: Reverse children list and make new heap H'

H' = [15 (degree 2), 28 (degree 1), 12 (degree 0)]
15 28 12
| |
25 33
|
41

Step 3: Union with remaining heap

Original H is now empty (only had root 7)
Result = H'

Final Heap:
15 28 12
 | |
25 33
|
41

Returned value: 7

3.8 Union Operation Example

Union of two heaps:

Heap H₁:
12 37 10
|
17

Degrees: [0, 1, 2]

Heap H₂:
25 7 6
| / /
28 24 8
|
14

Degrees: [1, 1, 2]

Step 1: Merge root lists by degree

Merged: [12(0), 25(1), 37(1), 6(2), 10(2)]

Step 2: Process same-degree trees

- 25 and 37 both have degree 1
→ Merge: 25 becomes child of 37 (37 > 25, so link)
25
/ \
28 37
|
17
Result: degree 2

- Now have: [12(0), 25(2), 6(2), 10(2)]

- 25 and 6 both have degree 2

→ Merge: 6 becomes root (6 < 25)
6
/|\
8 14 25
/ \
28 37
|
17
Result: degree 3

- Now have: [12(0), 6(3), 10(2)]

Final Heap after Union:

12 6 10
/|\
8 25 14
/ \
28 37
|
17

3.9 Comparison with Other Heaps

 Operation Binary Heap Binomial Heap Fibonacci Heap

Structure Complete Binary Tree Forest of Binomial Trees Forest of Heap-Ordered Trees

O(log n) O(log n)
Insert O(1)
(O(1) amortized) (O(1) amortized)

Find Min O(1) O(log n) O(1)

Extract Min O(log n) O(log n) O(log n) amortized

Union O(n) O(log n) O(1)

Decrease Key O(log n) O(log n) O(1) amortized

Delete O(log n) O(log n) O(log n) amortized

Simple priority queue, heap Frequent merging of Dijkstra's algorithm, Prim's

Best Use Case
sort heaps MST

3.10 Applications of Binomial Heap

1. Priority Queues: When frequent merge operations are needed
2. Discrete Event Simulation: Managing event queues
3. Dijkstra's Algorithm: Can be used instead of binary heap
4. Prim's MST Algorithm: Efficient with decrease-key operations
5. Best-First Search: In AI and game theory applications
6. Huffman Coding: When merging frequency trees
7. Job Scheduling: In operating systems

3.11 Advantages and Disadvantages

Advantages:

Efficient Union operation: O(log n) vs O(n) in Binary Heap

Good for mergeable heap applications
All operations are O(log n) in worst case
Flexible structure - can grow and shrink efficiently
Good cache performance for larger datasets

Disadvantages:

More complex implementation than Binary Heap

Find-Min is O(log n) vs O(1) in Binary Heap
Higher constant factors in practice
More pointer overhead (parent, child, sibling)
Not as cache-friendly as array-based Binary Heap for small datasets
3.12 Practice Problems

Problem 1: A binomial heap has 25 elements. What is the maximum number of

binomial trees it can have?

Solution: 25 in binary = 11001₂

This means: 1×B₄ + 1×B₃ + 0×B₂ + 0×B₁ + 1×B₀
Maximum trees = 3 trees (B₄, B₃, and B₀)

Problem 2: What is the time complexity to insert n elements into an initially empty
binomial heap?

Solution: Each insert takes O(log n) in worst case

Total: n × O(log n) = O(n log n)
However, amortized cost per insert is O(1), so total amortized = O(n)

Problem 3: How many nodes are at depth 2 in a binomial tree B₅?

Solution: Using binomial coefficient formula: ₅C₂ = 5!/(2!×3!) = 10 nodes

Problem 4: Compare the time taken to merge two heaps of size n each using
Binary Heap vs Binomial Heap.

Solution:
Binary Heap: Create new heap and insert all 2n elements = O(2n) = O(n)
Binomial Heap: Union operation = O(log n)
Binomial Heap is significantly faster for merging!

End of Lecture Notes

Design and Analysis of Algorithms
Topics: Algorithm Analysis • Complexity Theory • Binomial Heap