DAA - 3
Sunday, April 27, 2025 8:23 AM
Unit 3: Divide and Conquer Algorithms (8 Hrs)
3.1 Searching Algorithms
Binary Search
• Define binary search algorithm.
• Write recursive binary search algorithm and analyze its time complexity.
• Design binary search algorithm and analyze it.
Min-Max Finding
• Write down min-max algorithm and analyze its complexity.
• Write an algorithm to find the maximum element of an array and analyze its time complexity.
3.2 Sorting Algorithms
Merge Sort
• Write the algorithm for merge sort and find its time complexity.
• Explain merge-sort algorithm with an example and analyze time complexity.
• Compare merge sort with quick sort in terms of time and space complexity.
Quick Sort
• Write algorithm for quick sort and trace for given array (eg: {16,7,15,14,18,25,55,32}).
• Trace quick sort algorithm for array A[ ]={15,7,6,23,18,34,25}.
• Trace quick sort algorithm for array A[]={99,50,60,8,5,6,20,25,40}.
• What is quick sort? Trace with example.
• Explain quick sort randomized version and its time complexity.
• Write quick sort randomized algorithm and explain its complexity.
• What is the worst case of quick sort? How to optimize quick sort for worst case?
• Main idea of randomized algorithm? Write quick sort and analyze.
Heap Sort
• What is heap sort? Define heap.
• Trace heap sort for given arrays (Examples: {2,9,3,12,15,8,11}, {16,41,18,99,74,20,17,25,10},
{12,45,62,50,85,15,28}, {10,8,12,70,20,5,30}).
• Write algorithm for heap sort and find complexity analysis.
3.3 Order Statistics
Selection Problem
• What is order statistics?
• Define order statistics and select the ith largest element from an unordered list.
• How to solve selection problem in expected linear time.
• How to solve selection problem in worst case linear time.
• Explain worst-case linear time selection algorithm and analyze its complexity.
• Devise algorithm that guarantees selection of ith order statistics in linear time. Write and analyze.
Topics What To Study Importanc
e
Binary Search Definition, Recursive Algorithm, Time Complexity (imp)
Min-Max Min-Max Algorithm, Complexity (imp)
Finding
Merge Sort Algorithm, Example, Time and Space Complexity, Comparison with Quick Sort (imp)
Quick Sort Algorithm, Randomized Version, Trace Examples, Best/Worst/Average Case Complexity (imp)
Heap Sort Heap Definition, Heapify, Build Heap, Heap Sort Algorithm, Time Complexity (imp)
Order Statistics Order statistics Definition, Selection Algorithm (Expected and Worst Case Linear Time), (imp)
Time Complexity
Divide and Conquer
Divide and Conquer is a problem-solving strategy where a problem is:
• Divided into smaller subproblems,
• Each subproblem is conquered (solved) recursively,
• And their solutions are combined to solve the original problem.
It breaks a complex problem into simpler, smaller ones until they become easy to solve.
Steps in Divide and Conquer:
1. Divide:
Break the problem into smaller subproblems (same type as original).
2. Conquer:
Solve the subproblems recursively.
If subproblems are small enough, solve directly.
3. Combine:
Merge the solutions of the subproblems to form the solution of the original problem.
Binary Search
Binary Search is a searching algorithm used to find the position of a target element in a sorted array by repeatedly
dividing the search interval in half.
• It compares the target value to the middle element.
• If they are not equal, half of the array is eliminated.
• Works only on sorted data.
Recursive Binary Search Algorithm
1. Start
2. Read an array A of n elements (sorted in ascending order) from the user.
3. Read the key element x to be searched.
4. Initialize low = 0, high = n - 1.
5. Call the function BinarySearch(A, low, high, x).
6. Inside BinarySearch(A, low, high, x):
1. If low > high, then
6.1.1. Return "Element not found" and Exit.
2. Compute mid = (low + high) / 2.
3. If A[mid] == x, then
6.3.1. Return "Element found at position mid" and Exit.
4. Else If x < A[mid], then
6.4.1. Recursively call BinarySearch(A, low, mid - 1, x).
5. Else (x > A[mid]), then
6.5.1. Recursively call BinarySearch(A, mid + 1, high, x).
7. Stop
Recursive Binary Search Pseudocode:
BinarySearch(A, low, high, key)
if low > high
return -1
mid = (low + high) // 2
if A[mid] == key
return mid
else if A[mid] > key
return BinarySearch(A, low, mid - 1, key)
else
return BinarySearch(A, mid + 1, high, key)
Time Complexity Analysis:
Case Time Complexity
Best Case O(1) (key found at middle)
Average Case O(log n)
Worst Case O(log n)
Reason:
At each step, the array size is divided by 2.
Thus, the number of comparisons ≈ log₂(n).
Min-Max Finding Algorithm
In the Divide and Conquer approach for finding the Min and Max, we divide the array into two halves and recursively
find the minimum and maximum for each half. Then, we combine the results of the two halves to get the final Min and
Max.
Steps for Divide and Conquer Min-Max Finding:
1. Start
2. Base Case:
○ If the array has only one element, return the element as both the min and max.
○ If the array has two elements, return the smaller one as min and the larger one as max.
3. Divide:
○ Divide the array into two halves, left and right.
4. Conquer:
○ Recursively find the min and max for the left half of the array.
○ Recursively find the min and max for the right half of the array.
5. Combine:
○ Compare the min values from both halves to get the final min.
○ Compare the max values from both halves to get the final max.
6. Output:
○ Return the final min and max.
7. End
Min-Max Algorithm in Pseudo-Code:
DivideAndConquerMinMax(arr, low, high)
if low == high
return arr[low], arr[high]
else if high == low + 1
if arr[low] < arr[high]
return arr[low], arr[high]
else
return arr[high], arr[low]
mid = (low + high) / 2
leftMin, leftMax = DivideAndConquerMinMax(arr, low, mid)
rightMin, rightMax = DivideAndConquerMinMax(arr, mid + 1, high)
finalMin = min(leftMin, rightMin)
finalMax = max(leftMax, rightMax)
return finalMin, finalMax
Time Complexity Analysis:
• The algorithm divides the array into two halves, so the recurrence relation is:
○ T(n) = 2T(n/2) + O(1) (constant time for the comparison between the min and max).
• Solving this recurrence relation using the Master Theorem gives:
○ T(n) = O(n).
• So, the time complexity of this algorithm is O(n).
Number of Comparisons:
• For each pair of elements, we do 1 comparison for min and 1 comparison for max, leading to 2 comparisons for
each pair.
• The total number of comparisons will be proportional to the number of elements in the array.
Example to Trace:
Let’s trace the algorithm for the array:
A = [5, 2, 9, 1, 6, 7, 3]
1. Divide the array:
○ Left half: [5, 2, 9]
○ Right half: [1, 6, 7, 3]
2. Left half ([5, 2, 9]):
○ Divide into [5] and [2, 9].
○ For [5], min = max = 5.
○ For [2, 9], compare and find min = 2, max = 9.
○ Combine: min = 2, max = 9.
3. Right half ([1, 6, 7, 3]):
○ Divide into [1, 6] and [7, 3].
○ For [1, 6], compare and find min = 1, max = 6.
○ For [7, 3], compare and find min = 3, max = 7.
○ Combine: min = 1, max = 7.
4. Combine both halves:
○ min = min(2, 1) = 1, max = max(9, 7) = 9.
Final result:
Min = 1, Max = 9.
Merge Sort Algorithm:
Merge Sort is a classic Divide and Conquer algorithm. It works by dividing the input array into two halves, recursively
sorting both halves, and then merging the sorted halves to produce the sorted array.
Steps of the Merge Sort Algorithm:
1. Split:
• Divide the array into two halves, until each subarray contains only one element (which is trivially sorted).
2. Merge:
• Merge the subarrays back together in sorted order.
Merge Sort Algorithm (Recursive):
Algorithm (in steps):
1. Start
2. Check if the size of the array is greater than 1:
○ If no, return the array (base case, already sorted).
○ If yes, proceed with splitting.
3. Split the array into two halves:
○ Find the middle index: mid = n // 2 (where n is the size of the array).
○ Left subarray: arr[0:mid]
○ Right subarray: arr[mid:]
4. Recursively sort both halves:
○ Call Merge Sort on arr[0 to mid-1]
○ Call Merge Sort on arr[mid to end]
5. Merge the two sorted halves:
○ Merge the two subarrays into a single sorted array.
6. Return the sorted array.
7. End
Pseudocode :
MergeSort(A)
if length of A > 1:
mid = length of A // 2 // Find the middle index
Left = A[0..mid-1] // Divide the array into left half
Right = A[mid..end] // Divide the array into right half
MergeSort(Left) // Recursively sort the left half
MergeSort(Right) // Recursively sort the right half
i=0 // Initialize index for Left
j=0 // Initialize index for Right
k=0 // Initialize index for the original array A
while i < length of Left and j < length of Right:
if Left[i] < Right[j]:
A[k] = Left[i] // Place smaller element in A
i=i+1
else:
A[k] = Right[j] // Place smaller element in A
j=j+1
k=k+1
while i < length of Left: // If there are remaining elements in Left
A[k] = Left[i]
i=i+1
k=k+1
while j < length of Right: // If there are remaining elements in Right
A[k] = Right[j]
j=j+1
k=k+1
Time Complexity of Merge Sort:
• Best Case: O(nlogn)
• Average Case: O(nlogn)
• Worst Case: O(nlogn)
In each level of recursion, the array is split into two halves, and this splitting happens logn times. For each level, the
merging operation involves n comparisons. Thus, the total time complexity is O(nlogn).
Space Complexity:
• Space Complexity: O(n)
This is because, during the merge process, additional space is needed to store the left and right halves of the array at
each recursive level. So, the space complexity is linear with respect to the size of the array.
Trace Merge Sort with a Large Example:
Let's consider an array of size 8:
A = [38, 27, 43, 3, 9, 82, 10, 1]
Step-by-Step Tracing:
1. Initial Array:
A = [38, 27, 43, 3, 9, 82, 10, 1]
2. Divide the Array (Splitting): Split it into two halves:
Left: [38, 27, 43, 3]
Right: [9, 82, 10, 1]
3. Further Splitting:
○ Left subarray [38, 27, 43, 3] splits into:
Left: [38, 27]
Right: [43, 3]
○ Right subarray [9, 82, 10, 1] splits into:
Left: [9, 82]
Right: [10, 1]
4. Base Case (Single Elements):
○ [38, 27] splits into [38] and [27].
○ [43, 3] splits into [43] and [3].
○ [9, 82] splits into [9] and [82].
○ [10, 1] splits into [10] and [1].
5. Merging:
○ Merge [38] and [27] to form [27, 38].
○ Merge [43] and [3] to form [3, 43].
○ Merge [9] and [82] to form [9, 82].
○ Merge [10] and [1] to form [1, 10].
6. Further Merging:
○ Merge [27, 38] and [3, 43] to form [3, 27, 38, 43].
○ Merge [9, 82] and [1, 10] to form [1, 9, 10, 82].
7. Final Merge:
○ Merge [3, 27, 38, 43] and [1, 9, 10, 82] to form the final sorted array:
[1, 3, 9, 10, 27, 38, 43, 82]
Final Sorted Array:
[1, 3, 9, 10, 27, 38, 43, 82]
Quick Sort Algorithm
Quick Sort is a divide-and-conquer algorithm that works by selecting a pivot element from the array and partitioning the
other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are
then sorted recursively.
Quick Sort Algorithm (in Steps):
1. Start
2. Check if the array has more than one element:
○ If no, return the array (base case).
○ If yes, proceed with partitioning.
3. Choose a pivot element (common choices are:
○ First element
○ Last element
○ Middle element
○ Random element).
4. Partition the array:
○ Rearrange the elements such that all elements less than the pivot come before it, and all elements greater
than the pivot come after it.
○ The pivot will be in its correct position in the sorted array.
5. Recursively apply Quick Sort:
○ Call Quick Sort on the left subarray (elements less than pivot).
○ Call Quick Sort on the right subarray (elements greater than pivot).
6. End
Quick Sort Pseudocode:
Algorithm QuickSort(A, low, high)
1. If low < high:
a. pivot_index = Partition(A, low, high)
b. QuickSort(A, low, pivot_index - 1) // Recursively sort left subarray
c. QuickSort(A, pivot_index + 1, high) // Recursively sort right subarray
Algorithm Partition(A, low, high)
1. Set pivot = A[high]
2. Set i = low - 1
3. For j = low to high - 1:
a. If A[j] <= pivot:
i=i+1
Swap A[i] with A[j]
4. Swap A[i + 1] with A[high] // Move pivot to its correct position
5. Return i + 1 // Index of pivot
Example of Quick Sort Trace:
Let’s sort the array: [15, 7, 6, 23, 18, 34, 25].
Step 1: Partitioning the array
1. Choose the pivot: Suppose we choose the last element 25 as the pivot.
2. Partition the array:
○ Arrange elements such that numbers smaller than 25 come to the left and those greater than 25 come to
the right.
○ After partitioning, the array looks like: [15, 7, 6, 23, 18, 25, 34]. The pivot 25 is in its correct position.
○ Pivot index: 5
Step 2: Recursively apply Quick Sort
1. Left subarray: [15, 7, 6, 23, 18]
2. Right subarray: [34] (which is already sorted because it contains only one element).
Recursion on Left Subarray:
1. Choose pivot: Let's choose 18 as the pivot.
2. Partition the array: The partition results in: [15, 7, 6, 18, 23].
3. Recursively apply Quick Sort on the left and right subarrays:
○ Left subarray: [15, 7, 6]
○ Right subarray: [23] (already sorted).
Repeat the process recursively until all subarrays are sorted.
The final sorted array will be: [6, 7, 15, 18, 23, 25, 34].
Time Complexity:
Best Case: O(n log n) (When the pivot divides the array into two nearly equal halves at each recursion)
Average Case: O(n log n) (On average, the pivot divides the array into balanced subarrays)
Worst Case: O(n^2) (When the pivot is the smallest or largest element, leading to unbalanced subarrays)
Space Complexity:
Space Complexity: O(log n) (The space required for recursive stack space in the best and average cases)
Worst Case Space: O(n) (When the partitioning is highly unbalanced, the recursive depth can be O(n))
Randomized Quick Sort
Concept: Randomized Quick Sort is a variant of the traditional Quick Sort algorithm where instead of choosing a fixed
pivot (like the first element or middle element), a random element from the array is chosen as the pivot.
Steps:
1. Pick a Random Pivot: Choose a random element as the pivot.
2. Partition: Rearrange the elements such that elements less than the pivot come before it and elements greater
come after it.
3. Recursively Sort: Apply the same procedure recursively to the left and right subarrays created by the pivot.
Short Traced Example
Let’s trace the Randomized Quick Sort with the array:
Array: [10, 7, 8, 9, 1, 5]
Step 1: Initial Call
• Input Array: [10, 7, 8, 9, 1, 5]
• Pivot: Randomly chosen, suppose 9.
Swap pivot 9 with the last element 5:
Array: [10, 7, 8, 5, 1, 9]
Partitioning:
• 10 > 9, no swap.
• 7 < 9, swap 7 and 10: [7, 10, 8, 5, 1, 9]
• 8 < 9, swap 8 and 10: [7, 8, 10, 5, 1, 9]
• 5 < 9, swap 5 and 10: [7, 8, 5, 10, 1, 9]
• 1 < 9, swap 1 and 10: [7, 8, 5, 1, 10, 9]
After partition, pivot 9 is placed at index 4:
Array: [7, 8, 5, 1, 9, 10]
Step 2: Recursively Sort Left Subarray [7, 8, 5, 1]
• Pivot: Randomly chosen, suppose 8.
• Array: [7, 8, 5, 1]
• Swap pivot 8 with 1:
Array: [7, 1, 5, 8]
Partitioning:
• 7 < 8, no swap.
• 1 < 8, no swap.
• 5 < 8, no swap.
Pivot 8 is placed at index 3:
Array: [7, 1, 5, 8]
Step 3: Recursively Sort Left Subarray [7, 1, 5]
• Pivot: Randomly chosen, suppose 1.
• Array: [7, 1, 5]
• Swap pivot 1 with 5:
Array: [5, 1, 7]
Partitioning:
• 5 > 1, swap 5 and 1:
Array: [1, 5, 7]
Pivot 1 is placed at index 0:
Array: [1, 5, 7]
Step 4: Recursively Sort Right Subarray [5, 7]
• Pivot: Randomly chosen, suppose 7.
• No change needed, pivot 7 is placed at index 2:
Array: [1, 5, 7]
Step 5: Recursively Sort Right Subarray [10]
• Base case reached, no sorting needed.
Final Sorted Array:
Sorted Array: [1, 5, 7, 8, 9, 10]
Complexity:
• Best & Average Case: O(n log n)
• Worst Case: O(n²)
• Space Complexity: O(log n) for recursive call stack
Time Complexity of Heap Sort:
• Build Heap: O(n)
• Heapify: O(log n) (applies to each element in the heap)
• Overall Time Complexity: O(n log n) (for both sorting and building the heap)
• Space Complexity: O(1) (in-place sorting)
Order Statistics
Order statistics refers to the process of selecting the k-th smallest or k-th largest element in an unsorted array. For
example:
• The 1st order statistic (k=1) is the smallest element in the array.
• The 2nd order statistic (k=2) is the second smallest element, and so on.
In general, Order Statistic is the k-th smallest element in an unsorted list.
Example 1: Find the 2nd Smallest Element (2nd Order Statistic)
Array: [12, 3, 5, 7, 19]
1. Sort the array: [3, 5, 7, 12, 19]
2. The 2nd smallest element is 5. So, the 2nd order statistic is 5.
Two Methods for Finding Order Statistics:
1. Selection in Expected Linear Time (Randomized Selection)
2. Selection in Worst-Case Linear Time (Deterministic Selection)
1. Selection in Expected Linear Time (Randomized Selection)
Randomized Selection is an algorithm used to find the k-th smallest element (or the k-th order statistic) in an unsorted
list in expected linear time.
Unlike sorting, which requires O(n log n) time, randomized selection can find the k-th smallest element in O(n) time on
average.
How Randomized Selection Works:
The algorithm is based on Randomized QuickSort (or the partitioning technique in QuickSort), where we:
1. Choose a pivot element randomly.
2. Partition the array around this pivot.
3. Recursively focus on the part of the array that contains the k-th smallest element.
Steps of the Randomized Selection Algorithm:
1. Start
2. Choose a pivot element randomly from the array.
3. Partition the array around the pivot such that:
○ All elements less than the pivot are on the left.
○ All elements greater than the pivot are on the right.
4. Let the pivot's index be i.
○ If i+1 == k, return the pivot (because it's the k-th smallest element).
○ If k < i+1, recursively apply the algorithm on the left subarray (elements smaller than the pivot).
○ If k > i+1, recursively apply the algorithm on the right subarray (elements greater than the pivot).
5. End
Time Complexity:
• Expected Time Complexity: O(n)
○ Each partitioning step divides the array into two parts and proceeds with the smaller part. On average, the
number of elements to be processed in each recursive call decreases in half.
○ This results in a linear time complexity on average.
• Worst-case Time Complexity: O(n^2) (when the pivot is always the smallest or largest element, causing an
unbalanced partition).
○ However, since the pivot is chosen randomly, the expected time complexity is still O(n).
Example:
Array: [12, 3, 5, 7, 19], and we want to find the 3rd smallest element (k = 3).
1. Step 1: Randomly choose a pivot. Let's pick 5 as the pivot.
2. Step 2: Partition the array around 5:
○ Left side: [3] (elements less than 5)
○ Pivot: [5]
○ Right side: [12, 7, 19] (elements greater than 5)
After partitioning:
○ Array: [3, 5, 12, 7, 19]
○ Pivot is at index 1.
3. Step 3: The pivot is at index 1 (which is the 2nd smallest element). We want the 3rd smallest element (k = 3).
○ Since k = 3 is greater than the pivot index (1), we now focus on the right subarray [12, 7, 19].
4. Step 4: Randomly choose a pivot from [12, 7, 19]. Let's choose 7 as the pivot.
5. Step 5: Partition the array around 7:
○ Left side: [] (no elements less than 7)
○ Pivot: [7]
○ Right side: [12, 19] (elements greater than 7)
After partitioning:
○ Array: [3, 5, 7, 12, 19]
○ Pivot 7 is at index 2.
6. Step 6: The pivot is at index 2, which is exactly the 3rd smallest element in the array.
Thus, the 3rd smallest element is 7.
2. Selection in Worst-Case Linear Time (Deterministic Selection)
Deterministic Selection uses the Median of Medians algorithm to find the k-th smallest element in worst-case linear
time (O(n)).
Steps:
1. Divide the array into groups of 5 elements.
2. Sort each group and find the median of each group.
3. Recursively find the median of the medians (median of the group medians).
4. Partition the array around the median of medians.
5. Depending on the pivot’s position:
○ If it's the k-th smallest, return it.
○ Otherwise, recursively search the appropriate half.
Example:
Given Example:
We are tasked with finding the 3rd smallest element in the array:
[12, 3, 5, 7, 19, 2, 10, 18, 1, 6]
Step 1: Divide the array into groups of 5
We start by dividing the given array into groups of 5 elements each. If the number of elements isn't a multiple of 5, the
last group may have fewer than 5 elements.
Array: [12, 3, 5, 7, 19, 2, 10, 18, 1, 6]
Divide this into 2 groups of 5:
• Group 1: [12, 3, 5, 7, 19]
• Group 2: [2, 10, 18, 1, 6]
Step 2: Find the median of each group
We now find the median of each group. Recall that the median of a group is the middle element when the group is
sorted.
Group 1: [12, 3, 5, 7, 19]
1. Sort the elements in the group: [3, 5, 7, 12, 19]
2. The middle element is the 3rd element (since there are 5 elements): 7
So, median of Group 1 = 7.
Group 2: [2, 10, 18, 1, 6]
1. Sort the elements in the group: [1, 2, 6, 10, 18]
2. The middle element is the 3rd element (since there are 5 elements): 6
So, median of Group 2 = 6.
Step 3: Form a new list of the medians
Now, we take the medians from each group and form a new list of these medians.
Medians of the groups: [7, 6]
Step 4: Find the median of the medians
We now need to find the median of the medians (i.e., the median of the list [7, 6]).
• Since there are only two elements (7 and 6), the median is the lower of the two: 6.
So, median of the medians = 6.
Step 5: Partition the array around the median of medians
Now, we use the median of medians (6) as the pivot to partition the original array into two parts:
• One part with elements less than 6.
• One part with elements greater than 6.
Partitioning around the median of medians (6) gives us the following:
Array: [12, 3, 5, 7, 19, 2, 10, 18, 1, 6]
• Elements less than 6: [3, 5, 2, 1]
• Elements greater than 6: [12, 7, 19, 10, 18]
Now, after partitioning, we know that:
• The 3rd smallest element must be among the elements that are less than 6, because we're looking for the 3rd
smallest element, and the partitioning ensures that the first 4 elements (which are the smallest) are all smaller
than 6.
So, we now focus on the subarray [3, 5, 2, 1].
Step 6: Repeat the process on the smaller subarray
We need to find the 3rd smallest element from the subarray [3, 5, 2, 1]. Since this subarray has 4 elements, we will
continue the same process:
Find the median of the subarray [3, 5, 2, 1]:
• Sort the subarray: [1, 2, 3, 5]
• The middle element is the 2nd element, which is 2.
Thus, the median of the subarray [3, 5, 2, 1] is 2.
Step 7: Partition around the new median (2)
We partition the array around 2:
• Elements less than 2: [1]
• Elements greater than 2: [3, 5]
Now, we have a smaller array: [3, 5].
Step 8: Identify the 3rd smallest element
At this point, we know that the 3rd smallest element in the original array is 3, because:
Time Complexity:
• Worst Case: O(n)
• Average Case: O(n)
This algorithm guarantees O(n) time complexity even in the worst case, unlike randomized algorithms.
Space Complexity:
• O(n) (for storing medians and recursive calls)