PPT: Divide & Conquer | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Divide and 
Conquer
Page 2


Divide and 
Conquer
Advantages and Disadvantages
Advantages
Simplifies complex problems 
by breaking them down
Often achieves optimal time 
complexity (e.g., O(n log n) for 
sorting)
Naturally parallelisable 
(subproblems are 
independent)
Disadvantages
Recursive overhead (stack 
space)
May require extra memory for 
combining solutions
Not always intuitive for all 
problems
Use Cases
Sorting, searching, matrix 
operations
Geometric problems
Problems with independent 
subproblems
The divide and conquer approach shines when problems can be broken into independent subproblems 
with efficient merge steps. While it offers significant performance benefits for many algorithms, it's 
important to consider the trade-offs in terms of memory usage and implementation complexity.
Page 3


Divide and 
Conquer
Advantages and Disadvantages
Advantages
Simplifies complex problems 
by breaking them down
Often achieves optimal time 
complexity (e.g., O(n log n) for 
sorting)
Naturally parallelisable 
(subproblems are 
independent)
Disadvantages
Recursive overhead (stack 
space)
May require extra memory for 
combining solutions
Not always intuitive for all 
problems
Use Cases
Sorting, searching, matrix 
operations
Geometric problems
Problems with independent 
subproblems
The divide and conquer approach shines when problems can be broken into independent subproblems 
with efficient merge steps. While it offers significant performance benefits for many algorithms, it's 
important to consider the trade-offs in terms of memory usage and implementation complexity.
Binary Search
Divide
Find the middle element of the array
Conquer
Compare middle element with target; if equal, return index. if target < middle, recurse on left half; if 
target > middle, recurse on right half
Combine
No combination needed (single element found)
Binary search efficiently finds elements in sorted arrays with O(log n) time complexity by halving the search space 
in each step. For example, in array [1, 3, 5, 7, 9], to find target 7, we first check mid=5, then search [7, 9], and find 7. 
This algorithm can be implemented recursively (O(log n) space) or iteratively (O(1) space).
Page 4


Divide and 
Conquer
Advantages and Disadvantages
Advantages
Simplifies complex problems 
by breaking them down
Often achieves optimal time 
complexity (e.g., O(n log n) for 
sorting)
Naturally parallelisable 
(subproblems are 
independent)
Disadvantages
Recursive overhead (stack 
space)
May require extra memory for 
combining solutions
Not always intuitive for all 
problems
Use Cases
Sorting, searching, matrix 
operations
Geometric problems
Problems with independent 
subproblems
The divide and conquer approach shines when problems can be broken into independent subproblems 
with efficient merge steps. While it offers significant performance benefits for many algorithms, it's 
important to consider the trade-offs in terms of memory usage and implementation complexity.
Binary Search
Divide
Find the middle element of the array
Conquer
Compare middle element with target; if equal, return index. if target < middle, recurse on left half; if 
target > middle, recurse on right half
Combine
No combination needed (single element found)
Binary search efficiently finds elements in sorted arrays with O(log n) time complexity by halving the search space 
in each step. For example, in array [1, 3, 5, 7, 9], to find target 7, we first check mid=5, then search [7, 9], and find 7. 
This algorithm can be implemented recursively (O(log n) space) or iteratively (O(1) space).
Merge Sort
1 Divide
Split array into two halves
2 Conquer
Recursively sort each half
3 Combine
Merge sorted halves into a single sorted array
Merge sort is a stable sorting algorithm with predictable O(n log n) 
time complexity. For example, with array [5, 2, 8, 1], we divide into 
[5, 2] and [8, 1], recursively sort to get [2, 5] and [1, 8], then merge to 
form [1, 2, 5, 8].
While merge sort guarantees consistent performance regardless of 
input data, it requires O(n) additional space for the temporary 
array used during merging, making it less memory-efficient than 
some alternatives.
Page 5


Divide and 
Conquer
Advantages and Disadvantages
Advantages
Simplifies complex problems 
by breaking them down
Often achieves optimal time 
complexity (e.g., O(n log n) for 
sorting)
Naturally parallelisable 
(subproblems are 
independent)
Disadvantages
Recursive overhead (stack 
space)
May require extra memory for 
combining solutions
Not always intuitive for all 
problems
Use Cases
Sorting, searching, matrix 
operations
Geometric problems
Problems with independent 
subproblems
The divide and conquer approach shines when problems can be broken into independent subproblems 
with efficient merge steps. While it offers significant performance benefits for many algorithms, it's 
important to consider the trade-offs in terms of memory usage and implementation complexity.
Binary Search
Divide
Find the middle element of the array
Conquer
Compare middle element with target; if equal, return index. if target < middle, recurse on left half; if 
target > middle, recurse on right half
Combine
No combination needed (single element found)
Binary search efficiently finds elements in sorted arrays with O(log n) time complexity by halving the search space 
in each step. For example, in array [1, 3, 5, 7, 9], to find target 7, we first check mid=5, then search [7, 9], and find 7. 
This algorithm can be implemented recursively (O(log n) space) or iteratively (O(1) space).
Merge Sort
1 Divide
Split array into two halves
2 Conquer
Recursively sort each half
3 Combine
Merge sorted halves into a single sorted array
Merge sort is a stable sorting algorithm with predictable O(n log n) 
time complexity. For example, with array [5, 2, 8, 1], we divide into 
[5, 2] and [8, 1], recursively sort to get [2, 5] and [1, 8], then merge to 
form [1, 2, 5, 8].
While merge sort guarantees consistent performance regardless of 
input data, it requires O(n) additional space for the temporary 
array used during merging, making it less memory-efficient than 
some alternatives.
Quick Sort
Quick sort selects a pivot and partitions the array into elements less than and greater than the pivot, then recursively sorts the 
subarrays. With the array [5, 2, 8, 1] and pivot 5, we partition to [2, 1, 5, 8] with 5 in the correct position and continue sorting.
While quick sort achieves O(n log n) average time complexity and uses O(log n) space, its performance degrades to O(n²) in worst 
cases. The algorithm is in-place but unstable, with pivot selection being critical to performance.
Select Pivot
Choose an element as pivot
Partition
Rearrange elements around pivot
Recursive Sort
Sort subarrays independently