UNIT 2.

0 Part 1 of 2

Pseudo Code :
• is step-by-step description of an algorithm written in a way that
is easy for humans to understand, but not strict like programming
syntax.
• Acts as a bridge between algorithm (theory) and programming
(implementation).
• Uses simple English + mathematical/logical notation.
• Focus is on logic, not syntax.
• Can be easily converted into any programming language.
Examples:
1. Linear Search
Algorithm LinearSearch(A, n, key)
1. for i ← 1 to n do
2. if A[i] = key then
3. return i
4. return "Not Found"

2. Finding Maximum Element in an Array

Algorithm FindMaximum(A, n)
1. max ← A[1]
2. for i ← 2 to n do
3. if A[i] > max then
4. max ← A[i]
5. return max

Divide and Conquer Paradigm

• It is an algorithm design paradigm.
• Breaks a problem into smaller subproblems (Divide).
• Solves the subproblems (usually with recursion) (Conquer).
• Combines the results of subproblems to get the final solution
(Combine).
• Commonly used in Merge Sort, Quick Sort, Binary Search, Strassen’s
Matrix Multiplication.

[Original Problem]
/ \
/ \
/ \
[Sub-problem 1] [Sub-problem 2]
/ \ / \
/ \ / \
[Sub-sub 1.1] [Sub-sub 1.2] ... ...
/ \ / \
/ \ / \
[Base Case] [Base Case] ... (until trivial problems are reached)

P a g e 1 | 15 U2_Part 1 of 2_DAA_GECS_2K23
1. Binary Search
• It is a Divide and Conquer algorithm.
• Works on a sorted array (ascending or descending).
• Idea: Repeatedly divide the array into halves and search only in
the relevant half.
• Steps:
1. Compare the middle element with the key.
2. If middle = key → success.
3. If key < middle → search left half.
4. If key > middle → search right half.
• Time Complexity: O(log n)
• Best Case: O(1) (if found at middle in first step).
• Worst Case: O(log n).
• Average Case: O(log n).
• Space Complexity: O(1) (iterative), O(log n) (recursive).

Algorithm:
Algorithm binarySearch(A, low, high, key)
1. if low > high then
2. return "Not Found"
3. mid ← (low + high) / 2
4. if A[mid] = key then
5. return mid
6. else if key < A[mid] then
7. return binarySearch(A, low, mid - 1, key)
8. else
9. return binarySearch(A, mid + 1, high, key)
Time Complexity : T(n) = constant + T(n/2)
= O (log n)

Example: (Key is 61)

P a g e 2 | 15 U2_Part 1 of 2_DAA_GECS_2K23
 Example 2:

P a g e 3 | 15 U2_Part 1 of 2_DAA_GECS_2K23
2. Merge Sort
•
It is a Divide and Conquer algorithm.
•
Works on any array (sorting is its purpose).
•
Idea: Recursively split the array into smaller sub-arrays until
each sub-array has a single element (which is trivially sorted).
Then, repeatedly merge these sorted sub-arrays to produce new,
larger sorted arrays until the entire array is merged.
• Steps:
1. Divide: Find the middle point to split the array into two
halves.
2. Conquer: Recursively call Merge Sort on the left half and the
right half.
3. Combine: Merge the two sorted halves back together into a
single sorted array. This is the critical step.
• Time Complexity: O(n log n) for all cases (best, average, worst).
• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)
• Space Complexity: O(n) (requires a temporary array for merging).
Algorithm:
Algorithm mergeSort(A, low, high)
1. if low < high then
2. mid ← low + (high - low) / 2 // Prevents overflow for large arrays
3. mergeSort(A, low, mid) // Recursively sort first half
4. mergeSort(A, mid + 1, high) // Recursively sort second half
5. merge(A, low, mid, high) // Merge the two sorted halves
Time Complexity: T(n) = T(n/2)+T(n/2)+n
= 2T(n/2)+n = O ([Link])

Algorithm merge(A, low, mid, high)

1. n1 ← mid - low + 1
2. n2 ← high - mid
3. Create temporary arrays L[0..n1] and R[0..n2]
4. for i ← 0 to n1-1 do // O (n/2)
5. L[i] ← A[low + i]
6. for j ← 0 to n2-1 do // O (n/2)
7. R[j] ← A[mid + 1 + j]
8. i ← 0, j ← 0, k ← low
9. while i < n1 and j < n2 do // O (n)
10. if L[i] <= R[j] then
11. A[k] ← L[i]
12. i ← i + 1
13. else
14. A[k] ← R[j]
15. j ← j + 1
16. k ← k + 1
17. while i < n1 do // Copy remaining elements of L[] – O(n/2)
18. A[k] ← L[i]
19. i ← i + 1
20. k ← k + 1
21. while j < n2 do // Copy remaining elements of R[]– O(n/2)
22. A[k] ← R[j]
23. j ← j + 1
24. k ← k + 1
Time Complexity: O (constant + n/2 + n/2 + n + n/2 + n/2)
= O (n)

P a g e 4 | 15 U2_Part 1 of 2_DAA_GECS_2K23
Example :
1. Split the array (left, right then merge)

2. Merge the left most sub array

3. Split the right sub array

P a g e 5 | 15 U2_Part 1 of 2_DAA_GECS_2K23
 4. Merge the right array

5. Again merge the array

6. Now the left sub array is sorted, do similarly for right sub
array

7. Merge both the sub array to get final result

P a g e 6 | 15 U2_Part 1 of 2_DAA_GECS_2K23
3. Quick Sort
•
It is a Divide and Conquer algorithm.
•
Works on any array (sorting is its purpose).
•
Idea: Choose a 'pivot' element and partition the array so that all
elements smaller than the pivot are on its left and all elements
greater are on its right. The pivot is now in its correct sorted
position. Recursively apply this process to the left and right sub-
arrays.
• Steps:
1. Divide: Select a pivot and partition the array around it. This
places the pivot in its final sorted position.
2. Conquer: Recursively apply Quick Sort to the left sub-array
(elements < pivot) and the right sub-array (elements > pivot).
3. Combine: Unlike Merge Sort, no combine step is needed because
the array is sorted in place as the partitions are created.
• Time Complexity:
• Best Case: O(n log n) (occurs when the pivot divides the array into
nearly equal halves each time).
• Average Case: O(n log n)
• Worst Case: O(n²) (occurs when the pivot is consistently the
smallest or largest element, e.g., an already sorted array with the
first/last element chosen as the pivot).
• Space Complexity: O(log n) on average for the recursion call stack.
Algorithm:
Algorithm quickSort(A, low, high)
1. if low < high then
2. pivot_index ← partition(A, low, high) // Pivot is placed in correct position
3. quickSort(A, low, pivot_index - 1) // Recursively sort left sub-array
4. quickSort(A, pivot_index + 1, high) // Recursively sort right sub-array
Time Complexity:
Best Case T(n) = partition + T(n/2) + T(n/2)
= n + 2T(n/2) = O(nlogn)
Average Case T(n) = partition + T(n/1000) + T(999.n/1000)
= O(nlogn)
Worst Case T(n) = partition + T(n-1)
= O (n2)

Algorithm partition(A, low, high)

// This function uses the last element (A[high]) as the pivot
1. pivot ← A[high]
2. i ← low - 1 // Index of smaller element, indicates right position of pivot
3. for j ← low to high - 1 do
4. if A[j] <= pivot then
5. i ← i + 1
6. swap A[i] and A[j]
7. swap A[i + 1] and A[high]
8. return i + 1
Time Complexity : O (constant + for loop + swap)
= O (c + n + c)
= O (n)
Example :

low=0, high=8, pivot=5

P a g e 7 | 15 U2_Part 1 of 2_DAA_GECS_2K23
After partition, p= 4

low=0, high=3, pivot=3

After partition, p= 2

low=0, high=1, pivot=1

After partition p=0

low=1, high=1, pivot=2 (do nothing)

Right partition of element 3

low=3, high=3, pivot=4 (do nothing)

P a g e 8 | 15 U2_Part 1 of 2_DAA_GECS_2K23
Right partition of element 5

low=5, high=8, pivot=7

After partition p=6

low=5, high=5, pivot=6 (do nothing)

Right partition of element 7

low=7, high=8, pivot=8

After partition p=7

low=8, high=8, pivot=9 (do nothing)

Array is sorted:

P a g e 9 | 15 U2_Part 1 of 2_DAA_GECS_2K23
4. Heap Sort
Heap :
A Heap is a specialized tree-based data structure that satisfies
the heap property. It is primarily implemented as a complete binary
tree.
Underlying Structure: A complete (or nearly complete) binary tree.
1. Heap Property: The tree must satisfy one of the following
properties:
o Max-Heap Property: The value of any node is greater than or
equal to the value of its children. A[Parent(i)] >= A[i].
o Min-Heap Property: The value of any node is less than or equal
to the value of its children. A[Parent(i)] <= A[i].
2. Representation: It is almost always implemented as an array. The
tree structure is implicit:
o For a node at index i (0-indexed):
▪ Parent Index: floor((i-1)/2)
▪ Left Child Index: 2*i + 1
▪ Right Child Index: 2*i + 2
3. Root Node: The root of the tree is the first element of the array
(A[0]).
o In a Max-Heap, the root is the maximum element.
o In a Min-Heap, the root is the minimum element.
4. Operations: Key operations (like INSERT, EXTRACT-MAX, INCREASE-
KEY) are designed to maintain the heap property and have a time
complexity of O(log n).
5. Building a Heap: An arbitrary array can be converted into a valid
heap in O(n) time using a bottom-up algorithm (BUILD-MAX-HEAP).

Heapsort :
Heapsort is a comparison-based, in-place sorting algorithm that uses the
properties of a heap to sort an array.
The algorithm consists of two main phases:
• Phase 1 - Build Heap: Transform the input array into a valid max-
heap. This places the largest element at the root (A[0]).
• Phase 2 - Sort:
o Extract Max: Repeatedly swap the root (current maximum
element) with the last element in the unsorted part of the
heap.
o Heapify: The swap places a small element at the root, violating
the heap property.
The MAX_HEAPIFY procedure is called on the root to restore the
heap structure.
• Complexity:
o Time Complexity: O(n log n) for all cases (best, average,
worst). The build phase is O(n), and the sort phase performs
n operations each costing O(log n).
o Space Complexity: O(1). It is an in-place algorithm, requiring
only a constant amount of additional memory for temporary
variables.

P a g e 10 | 15 U2_Part 1 of 2_DAA_GECS_2K23
Algorithm:
HEAPSORT(A,n)
1 BUILD-MAX-HEAP(A,n) // Phase 1: O(n)
2 while(n>1) // Phase 2: n-1 times
3 exchange A[0] with A[n-1] // Move max to its sorted position
4 n=n-1 // Decrease heap size
5 MAX-HEAPIFY(A, 0, n) // Restore heap property: O(log n)
Time Complexity = O (build heap + n times heapify)
= O (n + [Link])
= O (nlogn)

BUILD-MAX-HEAP(A, n)
1 // 'n' is the number of elements in array A
2 // Start from the last non-leaf node and go backwards to the root.
3 // The last non-leaf node is at index: floor(n/2) - 1
4 for i = floor(n/2) - 1 down to 0
5 MAX-HEAPIFY(A, i, n)

MAX-HEAPIFY(A, i, n)
// 'i' is the index of the node to heapify
// 'n' is the current size of the heap
1 l = 2*i+1
2 r = 2*i+2
3 largest = i
4
5 if (l < n and A[l] > A[largest])
6 largest = l
7 if (r < n and A[r] > A[largest])
8 largest = r
9
10 if (largest != i)
11 swap ( A[i] , A[largest] )
12 MAX-HEAPIFY(A, largest, n) // Recursively heapify the affected subtree
Time Complexity : O (constant + height of node i)
= O (log n)

The BUILD-MAX-HEAP algorithm calls MAX-HEAPIFY on all non-leaf nodes.

The total time complexity T(n) is the sum of the costs of all these
calls.

Cost of heapify on single node = O(log n) or O(height of node)

= O (h)

Cost of heapify on all nodes at height h

= (Number of nodes at height h) ⋅ O(h)
𝑛
= ⌈2ℎ+1 ⌉ ⋅ O(h)

𝑛
Cost of all nodes = ∑𝐻
ℎ=0 ⌈2ℎ+1 ⌉ ⋅ O(h)
ℎ
= O (n ⋅ ∑∞
ℎ=0 )
2ℎ . 2
𝑛 ℎ
= O ( 2 ⋅ ∑∞
ℎ=0 )
2ℎ
𝑛 ℎ
= O (2 ⋅ 2) [∵ ∑∞
ℎ=0 𝑐𝑜𝑛𝑣𝑒𝑟𝑔𝑒𝑠 𝑡𝑜 2 ]
2ℎ

= O (n)

P a g e 11 | 15 U2_Part 1 of 2_DAA_GECS_2K23
Example :

Heapify Non-leaf nodes.

90 is already max-heap.

Heapify node having 36.

swap 36 and 50

Heapify node having 36.

36 is already a max-heap.

P a g e 12 | 15 U2_Part 1 of 2_DAA_GECS_2K23
Heapify node having 75.

swap 75 and 90

Heapify node having 75.

75 is already a max-heap.

Heapify node having 38.

swap 38 and 99

Heapify node having 38.

swap 38 and 50

Heapify node having 38.

38 is already a max-heap.

P a g e 13 | 15 U2_Part 1 of 2_DAA_GECS_2K23
Sorting: (swap the root node element with last node element, reduce the
heap size, repeat until single element left in the heap)

swap 99 and 40, reduce heap size, then do heapify at node 0

swap 90 and 36, reduce heap size, then do heapify at node 0

swap 89 and 38, reduce heap size, then do heapify at node 0

swap 75 and 38, reduce heap size, then do heapify at node 0

swap 50 and 36, reduce heap size, then do heapify at node 0

P a g e 14 | 15 U2_Part 1 of 2_DAA_GECS_2K23
swap 40 and 38, reduce heap size, then do heapify at node 0

swap 38 and 36, reduce heap size, then do heapify at node 0

Last node, already sorted.

Sorted Array is now :

P a g e 15 | 15 U2_Part 1 of 2_DAA_GECS_2K23