Unit 5: Divide and Conquer

ALGORITHM DESIGN TECHNIQUES 

DIVIDE AND CONQUER

Divide and Conquer is an algorithm design technique that:

1. Divides the problem into smaller subproblems
2. Solves each subproblem recursively
3. Combines the results to get the final solution

Merge Sort

Merge Sort is a stable, comparison-based sorting algorithm that uses divide and conquer.

Working Steps

1. Divide array into two halves
2. Recursively sort both halves
3. Merge the sorted halves

Example

Array: 38 27 43 3 9 82 10

• Divide → {38 27 43} {3 9 82 10}
• Sort recursively
• Merge → {3 9 10 27 38 43 82}

Time Complexity

Case	Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Space Complexity

• O(n)

Advantages

• Stable sorting
• Guaranteed performance

Disadvantages

• Extra memory required

Applications

• Large datasets
• External sorting

Quick Sort

Quick Sort is a fast divide-and-conquer sorting algorithm that uses a pivot element.

Steps

1. Choose a pivot
2. Partition elements around pivot
3. Recursively apply on subarrays

Example

Array: 10 80 30 90 40 50 70
Pivot = 10
Result → {30 40 50 70} 10 {80 90}

Time Complexity

Case	Complexity
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

Space Complexity

• O(log n)

Advantages

• Very fast in practice
• In-place sorting

Disadvantages

• Worst-case poor performance

Applications

• System libraries
• Real-time applications

Matrix Multiplication: Strassen’s Algorithm

Problem

Traditional matrix multiplication takes O(n³) time.

Definition

Strassen’s Algorithm reduces matrix multiplication time using divide and conquer.

Concept

• Divide matrices into submatrices
• Perform 7 multiplications instead of 8

Time Complexity

• O(n^2.81)

Advantages

• Faster than classical method

Disadvantages

• Complex implementation
• Not suitable for small matrices

Applications

• Scientific computing
• Graphics processing

DYNAMIC PROGRAMMING

Dynamic Programming (DP) solves problems by:

• Breaking them into overlapping subproblems
• Storing results to avoid recomputation

Dijkstra’s Algorithm

Finds the shortest path from a single source to all other vertices in a weighted graph with non-negative weights.

Steps

1. Initialize distance array
2. Select vertex with minimum distance
3. Relax edges
4. Repeat

Time Complexity

• O(V²) (simple implementation)

Limitations

• Does not support negative weights

Applications

• GPS navigation
• Network routing

Bellman–Ford Algorithm

Finds shortest path even when negative weight edges exist.

Steps

1. Initialize distances
2. Relax all edges (V–1) times
3. Check for negative cycles

Time Complexity

• O(VE)

Advantages

• Detects negative cycles

Disadvantages

• Slower than Dijkstra

Applications

• Financial systems
• Routing protocols

All-Pairs Shortest Path: Warshall (Floyd–Warshall) Algorithm

Finds shortest paths between all pairs of vertices.

Technique

• Dynamic Programming
• Uses adjacency matrix

Formula

$$D[i][j]=min(D[i][j],D[i][k]+D[k][j])$$

Time Complexity

• O(V³)

Applications

• Network optimization
• Graph analysis

Longest Common Subsequence (LCS)

LCS finds the longest subsequence common to two strings.

Example

Strings:
X = ABCBDAB
Y = BDCAB
LCS = BCAB

Approach

• Dynamic Programming table

Time Complexity

• O(mn)

Applications

• DNA analysis
• File comparison
• Version control systems

GREEDY PROGRAMMING

Concept

Greedy algorithms make locally optimal choices at each step.

Prim’s Algorithm

Finds Minimum Spanning Tree (MST) of a connected weighted graph.

Approach

• Start with one vertex
• Add minimum cost edge

Time Complexity

• O(V²)

Applications

• Network design
• Cable layout

Kruskal’s Algorithm

Constructs MST by:

• Sorting edges by weight
• Adding edges without forming cycles

Time Complexity

• O(E log E)

Applications

• Road networks
• Electrical grids

Prim vs Kruskal

Feature	Prim	Kruskal
Approach	Vertex-based	Edge-based
Data Structure	Priority Queue	Union-Find
Best for	Dense graphs	Sparse graphs

Important MCA Exam Points

• Merge sort → stable, O(n log n)
• Quick sort → fastest average
• Dijkstra → no negative weights
• Bellman-Ford → detects negative cycles
• Warshall → all-pairs shortest path
• LCS → DP classic problem
• Prim & Kruskal → MST algorithms