Design and Analysis of Algorithms (4CSGC2051)

Module 2: Divide and Conquer

General method, Sum of n elements of array, Sorting using divide and conquer: Merge sort,
Quick sort, Analysis of quick sort, Binary search, Defective chess board, Multiplication of
largest integers, Strassen’s matrix multiplication, Advantages and Disadvantages of divide
and conquer.
What are divide conquer algorithms?
Divide and Conquer is an algorithmic paradigm, similar to Greedy and Dynamic
Programming. A typical Divide and Conquer algorithm solves a problem using the following
three steps.
1. Divide: Break the given problem into subproblems of same type. This step involves
breaking the problem into smaller sub-problems. Sub-problems should represent a
part of the original problem. This step generally takes a recursive approach to divide
the problem until no sub-problem is further divisible. At this stage, sub-problems
become atomic in nature but still represent some part of the actual problem.
2. Conquer: Recursively solve these sub-problems. This step receives a lot of smaller
sub-problems to be solved. Generally, at this level, the problems are considered
'solved' on their own.
3. Combine: Appropriately combine the answers. When the smaller sub-problems are
solved, this stage recursively combines them until they formulate a solution of the
original problem. This algorithmic approach works recursively and conquer & merge
steps works so close that they appear as one.
This method usually allows us to reduce the time complexity by a large extent.
Following are some standard algorithms that are of the Divide and Conquer algorithms
variety.
Binary Search is a searching algorithm. In each step, the algorithm compares the input
element (x) with the value of the middle element in array. If the values match, return the
index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs to
the left side of the middle element, else it recurs to the right side of the middle element.
Quicksort is a sorting algorithm. The algorithm picks a pivot element, rearranges the array
elements in such a way that all elements smaller than the picked pivot element move to the
left side of the pivot, and all greater elements move to the right side. Finally, the algorithm
recursively sorts the subarrays on left and right of pivot element.
Merge Sort is also a sorting algorithm. The algorithm divides the array into two halves,
recursively sorts them, and finally merges the two sorted halves. The time complexity of this
algorithm is O(nLogn), be it best case, average case or worst case. It's time complexity can be
easily understood from the recurrence equates to: T(n) = 2T(n/2) + n.
Closest Pair of Points The problem is to find the closest pair of points in a set of points in x-
y plane. The problem can be solved in O(n^2) time by calculating distances of every pair of
Design and Analysis of Algorithms (4CSGC2051)

points and comparing the distances to find the minimum. The Divide and Conquer algorithm
solves the problem in O(nLogn) time.
Strassen’s Algorithm is an efficient algorithm to multiply two matrices. A simple method to
multiply two matrices need 3 nested loops and is O(n^3). Strassen’s algorithm multiplies two
matrices in O(n^2.8974) time.
Note: Please refer to the example thought in classroom for Strassen multiplication.
Sum of n elements of Array:
To find the sum of n elements of an array using the divide and conquer method, you can
break down the problem into smaller subproblems, solve each subproblem recursively, and
then combine the results to get the final sum.
Design and Analysis of Algorithms (4CSGC2051)

Explanation:

1. Base Case: The base case occurs when left == right, meaning there is only one
element in the subarray. In this case, the function simply returns the value of that
element.
2. Divide: The array is divided into two halves by finding the midpoint middle =
(left + right) / 2.
3. Conquer: The function recursively calculates the sum of the left half (leftSum =
sumArray(arr, left, middle)) and the right half (rightSum = sumArray(arr,
middle + 1, right)).
4. Combine: The function then returns the sum of the two halves by combining the
results: return leftSum + rightSum.

Output:
If you run the above program with the array {1, 2, 3, 4, 5, 6}, the output will be:

Time Complexity Analysis

Time complexity measures the total number of operations an algorithm performs relative to
the input size n.

1. Recursive Division:
o The array is split into two halves at each step, so at each level of recursion, the
problem size is halved.
o This splitting continues until the base case is reached (when the array segment
has only one element).
Design and Analysis of Algorithms (4CSGC2051)

2. Number of Levels in Recursion:

o The recursion tree has log 2(n)\log_2(n)log2​(n) levels because the array size
is halved at each level.
o Each level of recursion does a constant amount of work: adding two numbers.
3. Total Work at Each Level:
o Even though the problem size is halved at each level, the total work across all
subproblems at any level is still proportional to n.
o For example, at the first level, there is 1 sum operation for the whole array; at
the second level, there are 2 sum operations for two halves of the array; and so
on.
4. Recurrence Relation:
o The time complexity can be expressed as: T(n)=2T(n2)+O(1)T(n) =
2T\left(\frac{n}{2}\right) + O(1)T(n)=2T(2n​)+O(1)
o Solving this recurrence using the Master Theorem or recursive tree method,
the solution is T(n)=O(n)T(n) = O(n)T(n)=O(n).

Conclusion: The time complexity of this Divide and Conquer approach is

O(n)O(n)O(n), meaning the algorithm performs a linear amount of work relative to
the size of the array.

Space Complexity Analysis

Space complexity measures the amount of memory an algorithm uses relative to the input
size n.

1. Recursion Stack:
o The primary space consumption in this algorithm comes from the recursion
stack.
o Each recursive call requires space on the stack, and in the worst case, the
maximum depth of the recursion is log 2(n)\log_2(n)log2​(n).
o No extra data structures are used, so the additional space required is only for
the recursive calls.
2. Memory Usage:
o At each level of the recursion tree, the algorithm uses constant space for
variables like left, right, mid, leftSum, and rightSum.
o The total space used is proportional to the depth of the recursion tree.

Conclusion: The space complexity is O(log n)O(\log n)O(logn), which corresponds

to the depth of the recursion tree.

Summary

 Time Complexity: O(n)O(n)O(n)

o The algorithm performs linear work across all levels of recursion, meaning it
scales linearly with the size of the array.
 Space Complexity: O(log n)O(\log n)O(logn)
o The space required is proportional to the depth of the recursion tree, which is
logarithmic relative to the size of the array.
Design and Analysis of Algorithms (4CSGC2051)

This analysis shows that while the Divide and Conquer approach offers a clear and structured
way to sum the elements of an array, it does not improve the time complexity compared to a
simple iterative approach. However, it does require additional space due to the recursive
nature of the algorithm.

Note: log(n) is the power to which you need to put 2 to get “n”. So logarithm base 2 of n
would be equal to y if and only if the number 2 to the power of y were equal to n. For
instance, this means that 1 is equal to the power that we need to put 2 to get one.

Sorting Algorithms using Divide and Conquer Method:

Quick Sort Algorithm:
QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an
element as a pivot and partitions the given array around the picked pivot by placing the pivot
in its correct position in the sorted array.
How does QuickSort work?
The key process in quickSort is a partition(). The target of partitions is to place the pivot (any
element can be chosen to be a pivot) at its correct position in the sorted array and put all
smaller elements to the left of the pivot, and all greater elements to the right of the pivot.
Partition is done recursively on each side of the pivot after the pivot is placed in its correct
position and this finally sorts the array.
Choice of Pivot:
There are many different choices for picking pivots.
 Always pick the first element as a pivot.
 Always pick the last element as a pivot (implemented below)
 Pick a random element as a pivot.
 Pick the middle as the pivot
Algorithm:
Design and Analysis of Algorithms (4CSGC2051)

Partition Algorithm:

Illustration of Quicksort:
Now, let's see the working of the Quicksort Algorithm.
To understand the working of quick sort, let's take an unsorted array. It will make the concept
more clear and understandable.
Let the elements of array are –

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] = 24,
a[right] = 27 and a[pivot] = 24.
Design and Analysis of Algorithms (4CSGC2051)

Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves
to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm starts
from left and moves to right.
As a[pivot] > a[left], so algorithm moves one position to right as –
Design and Analysis of Algorithms (4CSGC2051)

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves
one position to right as -

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot] and
a[left], now pivot is at left, i.e. –

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24,
a[right] = 29, and a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one position to
left, as –
Design and Analysis of Algorithms (4CSGC2051)

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot]
and a[right], now pivot is at right, i.e. –

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts
from left and move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing the
same element. It represents the termination of procedure.
Element 24, which is the pivot element is placed at its exact position.
Elements that are right side of element 24 are greater than it, and the elements that are left
side of element 24 are smaller than it.
Design and Analysis of Algorithms (4CSGC2051)

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-
arrays. After sorting gets done, the array will be –

Quicksort complexity:
1. Time Complexity

o Best Case Complexity - In Quicksort, the best-case occurs when the pivot element is
the middle element or near to the middle element. The best-case time complexity of
quicksort is T(n)=2T(n/2​)+O(n) that is O(n*logn). The best case occurs when the pivot
always divides the array into two equal halves. This can happen if the pivot is the
median element. Here, T(n) is the time taken to sort n elements, and O(n) is the time
taken to partition the array. Here, 2T(n/2​) is the time to solve two subproblems, each of
size n/2​. The factor of 2 comes from solving two subproblems.

o Average Case Complexity - The average case is when the pivot divides the array into
two subarrays of approximately equal size on average. This is the most common
scenario for Quick Sort with a good pivot selection strategy (like random pivoting or
median-of-three). T(n)=T(k)+T(n−k−1)+O(n). Where k is the size of one subarray and
n−k−1is the size of the other. . K value will be mostly closer n/2. The average case
time complexity of quicksort is O(n*logn).
o Worst Case Complexity - In quick sort, worst case occurs when the pivot element is
either greatest or smallest element. Suppose, if the pivot element is always the last
element of the array. When the pivot is the smallest or largest element, resulting in highly
unbalanced partitions (one subarray with n−1 elements and the other with 0 elements). This
can happen if the array is already sorted or reverse sorted. The worst case would occur
when the given array is sorted already in ascending or descending order. The
recurrence relation is T(n)=T(n−1)+O(n). The worst-case time complexity of
quicksort is O(n2).
Design and Analysis of Algorithms (4CSGC2051)

Though the worst-case complexity of quicksort is more than other sorting algorithms such
as Merge sort and Heap sort, still it is faster in practice. Worst case in quick sort rarely
occurs because by changing the choice of pivot, it can be implemented in different ways.
Worst case in quicksort can be avoided by choosing the right pivot element.
Space Complexity:
Best and Average Case:
 Recursion Depth: O(log n)
 Space Complexity: O(log n)
 This efficient space usage occurs when the problem is divided evenly or nearly evenly
at each step, resulting in a balanced recursion tree.
Worst Case:
 Recursion Depth: O(n)
 Space Complexity: O(n)
 This less efficient space usage occurs when the problem is divided unevenly, leading
to deep recursion and higher memory consumption.
Merge Sort:
Merge sort is a sorting technique based on divide and conquer technique. In Merge sort, we
divide the array recursively in two halves, until each sub-array contains a single element, and
then we merge the sub-array in a way that it results into a sorted array. merge() function
merges two sorted sub-arrays into one, wherein it assumes that array[l .. n] and arr[n+1 .. r]
are sorted.
Algorithm:

Working of Merge Sort:

Let the elements of array are –
Design and Analysis of Algorithms (4CSGC2051)

The whole process can be divided into two steps:

 Step 1: Dividing the array into two halves.
In this step, we are dividing the given array into two halves. Here the size of the array [6, 8,
2, 4, 1, 3] is 6 thus the value of mid will be (size of the array)/2 which equals 3.
The array will be divided into two arrays ranging from index[0, 3] (i.e. 0 to mid-1)
and index[3, 5]. Now we have two arrays [6, 8, 2] and [4, 1, 3] each of size 3.
Now again, we will follow the above step to divide the two arrays [6, 8, 2] and [4, 1, 3] into
two halves, respectively. In both cases, the size of the array is 3; thus the value of mid will
be 3/2, which equals 1 (The value will be 1.5 but the ceil value is taken becindex[0, 1]ause
the array indexes are integers). Now we will divide both the array into two haves of
size 2 and 1, respectively. Thus we will have two arrays [6, 8] and [2] for the array [6, 8,
2] and [4, 1] and [3] for the array [4, 1, 3].
We will keep repeating this step until we have an array of unit sizes.
 Step 2: Merging the arrays.
Now that we have individual arrays of unit size, the arrays will be merged in a manner that
the items in the merged array at every step are in sorted order. The merging of arrays will
occur in the opposite order of the way the arrays were divided, i.e. firstly the unit arrays will
be merged into the size of 2, then the arrays of the size of two will be merged into the size of
Design and Analysis of Algorithms (4CSGC2051)

4 and so on and eventually we will have two halves of the original array which will together
be merged into one sorted array.
In the first step the arrays [6] and [8] will be merged into array [6, 8]. Now the unit
array [2] will be merged with the array [6, 8] and end up in an array [2, 6, 8]. Similarly the
arrays [4] and [1] will be merged into the array [1, 4] and the arrays [1, 4] and [3] will merge
into [1, 3, 4].
Now in the final step, we will merge [2, 6, 8] and [1, 3, 4] such that it stores items in a sorted
manner. Thus we will have [1, 2, 3, 4, 6, 8]. In this way, the merge sort program in c will sort
the given array.

Merge sort complexity:

Time Complexity:

 Best Case Complexity - It occurs when there is no sorting required, i.e. the array is
already sorted. The best-case time complexity of merge sort is O(n*logn).
 Average Case Complexity - It occurs when the array elements are in jumbled order
that is not properly ascending and not properly descending. The average case time
complexity of merge sort is O(n*logn).
 Worst Case Complexity - It occurs when the array elements are required to be sorted
in reverse order. That means suppose you have to sort the array elements in ascending
order, but its elements are in descending order. The worst-case time complexity of
merge sort is O(n*logn).
Space Complexity:

Binary Search:
#include<stdio.h>
Design and Analysis of Algorithms (4CSGC2051)

#include<stdlib.h>
void main( )
{
int n, a[20], key, low, high, mid ;
printf(“Enter the length of an array:\n”);
scanf(“%d”, &n);
printf(“Enter the elements to an array:\n”);
for( i = 0; i < n ; i++ )
{
scanf(“%d”, &a[i] );
}
printf(“Enter the key element to be searched:\n”);
scanf(“%d”, &key);
low = 0;
high = n-1;
while( low < = high )
{
mid = (low + high) / 2;
if(key = = a[mid])
{
printf(“Element found at location: %d \n”, mid + 1 );
exit(0);
}
else if(key < a[mid])
high = mid – 1;
else
low = mid +1;
}
printf(“Key not found \n” );
}
Design and Analysis of Algorithms (4CSGC2051)

Output:
[Link] the length of array: 5
Enter the elements of an array: 10 20 30 40 50
Enter the key element to be searched: 30
Element found at location 3

ALGORITHM
Step 1 : Enter the length of array and the elements in the array and search key
Step 2:Initialize low(Lower bound)=0 and high(upper bound) = array_size- 1
Step 3 : Start iteration with condition set to low<=high
Step 4: Calculate mid = low+high/2
Step 5 : Check if search key is equal to mid element then goto step 9
Step 6 : Else check if key is less than mid element then goto step 7 , else goto step 8
Step 7 : Update high = mid – 1 and continue iteration
Step 8 : Update low=mid+1 and continue iteration
Step 9 : Print key is found at this location
Step 10 : If key is not found in the given array print “Key not Found “
Step 11 :Stop
Binary Search Using Recursive Method:
#include <stdio.h>
int binary_search(int arr[], int target, int left, int right) {
if (left > right) {
return -1; // Target is not present in the array
}

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

if (arr[mid] == key) {
return mid; // Target found
} else if (arr[mid] > key) {
Design and Analysis of Algorithms (4CSGC2051)

return binary_search (arr, key, left, mid - 1); // Search in the left half
} else {
return binary_search (arr, key, mid + 1, right); // Search in the right half
}
}

int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 7;
int result = binary_search(arr, key, 0, n - 1);
if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found in the array\n", target);
}

return 0;
}
Time Complexity
1. Best Case:
o The best case occurs when the key is found in the middle of the array during
the first iteration.
o Time Complexity: O(1)
2. Average Case:
o In the average case, the algorithm will repeatedly divide the array into halves.
This division process is logarithmic, where each division reduces the problem
size by half.
o If the array contains n elements, the number of comparisons needed is
proportional to the logarithm of n.
o Time Complexity: O(log n)
Design and Analysis of Algorithms (4CSGC2051)

3. Worst Case:
o The worst case occurs when the key is not present in the array or is found after
searching through the entire search space.
o Even in the worst case, the algorithm still performs in logarithmic time, as
each comparison effectively halves the search space.
o Time Complexity: O(log n)
Detailed Explanation
 Number of Comparisons:
o At each step, binary search compares the key to the middle element of the
array.
o The size of the array is halved with each comparison, so the maximum number
of comparisons needed to find the key or determine its absence is proportional
to the number of times you can halve the array until it becomes one element.
o Mathematically, this is log2​(n), where n is the number of elements in the array.
 Logarithmic Nature:
o The logarithmic time complexity O(log n) signifies that as the size of the array
grows, the number of operations grows much more slowly compared to the
size of the array. For instance, doubling the size of the array only adds one
additional comparison in binary search.
Summary
 Best Case Time Complexity: O(1)
 Average Case Time Complexity: O(logn)
 Worst Case Time Complexity: O(logn)
Binary search is highly efficient for searching in sorted arrays due to its logarithmic time
complexity, making it suitable for scenarios where quick lookups are essential.
Space Complexity:

 Iterative Binary Search Space Complexity: O(1)

 Recursive Binary Search Space Complexity: O(log n)

The iterative version of binary search is more memory-efficient in terms of space complexity,
while the recursive version uses space proportional to the depth of recursion.

Defective Chessboard Problem:

The Defective Chessboard problem is a classic problem involving a recursive tiling method.
The problem can be described as follows:
Problem Description:
Design and Analysis of Algorithms (4CSGC2051)

Given an 2k×2k where (k ≥1 with one square missing (defective), tile the board using L-
shaped tiles, where each tile covers exactly 3 squares.
Steps to Solve the Problem:
1. Divide the chessboard into four 2k−1×2k−1 quadrants.
2. Place an L-shaped tile at the centre of the board to cover three of the four quadrants,
excluding the quadrant with the defective square.
3. Recursively tile each of the four quadrants.
Algorithm for Defective Chess Board Problem:

Implementation in C:
Here is an implementation of the Defective Chessboard problem in C:
#include <stdio.h>
#include <math.h>
// Global tile number to label L-shaped tiles
int tile = 1;
Design and Analysis of Algorithms (4CSGC2051)

// Function to tile the defective chessboard

void tileBoard(int board[][128], int topRow, int topCol, int defectRow, int defectCol, int size)
{
// Base case: when size is 2x2, use an L-shaped tile
if (size == 2) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (topRow + i != defectRow || topCol + j != defectCol) {
board[topRow + i][topCol + j] = tile;
}
}
}
tile++;
return;
}

int subSize = size / 2;

int centerRow = topRow + subSize;
int centerCol = topCol + subSize;

// Place an L-shaped tile at the center

if (defectRow < centerRow && defectCol < centerCol) { // Defect in the top-left quadrant
tileBoard(board, topRow, topCol, defectRow, defectCol, subSize);
} else {
board[centerRow - 1][centerCol - 1] = tile;
tileBoard(board, topRow, topCol, centerRow - 1, centerCol - 1, subSize);
}

if (defectRow < centerRow && defectCol >= centerCol) { // Defect in the top-right
quadrant
Design and Analysis of Algorithms (4CSGC2051)

tileBoard(board, topRow, centerCol, defectRow, defectCol, subSize);

} else {
board[centerRow - 1][centerCol] = tile;
tileBoard(board, topRow, centerCol, centerRow - 1, centerCol, subSize);
}

if (defectRow >= centerRow && defectCol < centerCol) { // Defect in the bottom-left
quadrant
tileBoard(board, centerRow, topCol, defectRow, defectCol, subSize);
} else {
board[centerRow][centerCol - 1] = tile;
tileBoard(board, centerRow, topCol, centerRow, centerCol - 1, subSize);
}

if (defectRow >= centerRow && defectCol >= centerCol) { // Defect in the bottom-right
quadrant
tileBoard(board, centerRow, centerCol, defectRow, defectCol, subSize);
} else {
board[centerRow][centerCol] = tile;
tileBoard(board, centerRow, centerCol, centerRow, centerCol, subSize);
}

tile++;
}

int main() {
int k = 3; // Size of the board (2^k x 2^k)
int size = pow(2, k);
int board[128][128] = {0}; // Assuming max size of 128x128

int defectRow = 3; // Example defective square row

Design and Analysis of Algorithms (4CSGC2051)

int defectCol = 3; // Example defective square column

// Start the tiling process

tileBoard(board, 0, 0, defectRow, defectCol, size);

// Print the board

for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
printf("%2d ", board[i][j]);
}
printf("\n");
}

return 0;
}

Explanation:

1. Initialization:
o The tileBoard function is used to recursively divide and conquer the
problem.
o board is a 2D array representing the chessboard.
o topRow and topCol represent the top-left corner of the current sub-board.
o defectRow and defectCol represent the position of the defective square
within the current sub-board.
o size is the size of the current sub-board.
2. Base Case:
o When the size of the current sub-board is 2x2, place an L-shaped tile, and
label it with the current tile number.
3. Recursive Case:
o The board is divided into four quadrants, and an L-shaped tile is placed at the
center of the board.
o Depending on which quadrant contains the defective square, the tiling process
continues recursively for each quadrant.
4. Output:
o The board array is printed to show the placement of the tiles.
Design and Analysis of Algorithms (4CSGC2051)

Multiplication of Largest Integers:

The multiplication of large integers using divide and conquer is an efficient technique that is
notably faster than the traditional grade-school algorithm, especially for very large numbers.
One well-known algorithm that uses this approach is Karatsuba's algorithm.

Karatsuba’s Algorithm Overview

Karatsuba’s algorithm works by breaking down the multiplication of two large numbers into
smaller, more manageable parts. It does this by splitting the numbers into two halves and
performing three multiplications, followed by some additions.
Design and Analysis of Algorithms (4CSGC2051)

Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Utility function to find the maximum of two numbers

int max(int x, int y) {
return (x > y) ? x : y;
}
Design and Analysis of Algorithms (4CSGC2051)

// Utility function to multiply two numbers using Karatsuba algorithm

char *multiply(char *num1, char *num2) {
int n1 = strlen(num1);
int n2 = strlen(num2);
int n = max(n1, n2);
// Base case: single-digit multiplication
if (n == 1) {
int result = (num1[0] - '0') * (num2[0] - '0');
char *product = (char *)malloc(3);
sprintf(product, "%d", result);
return product;
}
// Make both numbers of equal length by padding with zeros
if (n1 < n) {
char *paddedNum1 = (char *)malloc(n + 1);
sprintf(paddedNum1, "%0*d%s", n - n1, 0, num1);
num1 = paddedNum1;
}
if (n2 < n) {
char *paddedNum2 = (char *)malloc(n + 1);
sprintf(paddedNum2, "%0*d%s", n - n2, 0, num2);
num2 = paddedNum2;
}

int half = n / 2;

// Split num1 into a1, a0 and num2 into b1, b0

char *a1 = strndup(num1, n - half);
char *a0 = strdup(num1 + n - half);
char *b1 = strndup(num2, n - half);
Design and Analysis of Algorithms (4CSGC2051)

char *b0 = strdup(num2 + n - half);

// Recursive multiplication
char *P1 = multiply(a1, b1);
char *P2 = multiply(a0, b0);

// (a1 + a0) * (b1 + b0)

int sum1 = atoi(a1) + atoi(a0);
int sum2 = atoi(b1) + atoi(b0);
char sum1Str[20], sum2Str[20];
sprintf(sum1Str, "%d", sum1);
sprintf(sum2Str, "%d", sum2);
char *P3 = multiply(sum1Str, sum2Str);

// P3 - P1 - P2
int P3MinusP1P2 = atoi(P3) - atoi(P1) - atoi(P2);
char P3MinusP1P2Str[20];
sprintf(P3MinusP1P2Str, "%d", P3MinusP1P2);

// Final result
int finalResult = atoi(P1) * pow(10, 2 * half) + P3MinusP1P2 * pow(10, half) + atoi(P2);
char *result = (char *)malloc(20);
sprintf(result, "%d", finalResult);

free(a1);
free(a0);
free(b1);
free(b0);
free(P1);
free(P2);
Design and Analysis of Algorithms (4CSGC2051)

free(P3);

return result;
}
int main() {
char num1[] = "1234";
char num2[] = "5678";

char *result = multiply(num1, num2);

printf("Product: %s\n", result);

free(result);
return 0;
}
Design and Analysis of Algorithms (4CSGC2051)

Considerations:
 This implementation works well for small numbers, but for larger numbers or more
accurate arithmetic operations, additional considerations like handling of carry,
negative numbers, and precision need to be added.
 For larger integers, it's recommended to use libraries like GMP (GNU Multiple
Precision Arithmetic Library) in C, which can handle arbitrarily large numbers more
efficiently.

Advantages of Divide and Conquer

1. Simplifies Complex Problems:

o By breaking down a large, complex problem into smaller, more manageable
subproblems, divide and conquer can simplify the problem-solving process.
This can make it easier to understand and solve difficult problems.
2. Efficiency:
o Divide and conquer can lead to more efficient algorithms, especially for
problems that can be naturally divided. Algorithms like Merge Sort and Quick
Sort are classic examples where divide and conquer leads to time complexity
improvements over naive methods.
3. Parallelism:
o Since the subproblems are solved independently, divide and conquer is well-
suited for parallel computing. Subproblems can be solved simultaneously on
different processors or threads, leading to potential speedups.
4. Optimal Substructure:
o Problems with an optimal substructure, where the optimal solution of the main
problem can be constructed efficiently from the optimal solutions of its
Design and Analysis of Algorithms (4CSGC2051)

subproblems, are well-suited for divide and conquer. This property often leads
to efficient and elegant algorithms.
5. Improved Memory Usage:
o In some cases, divide and conquer can lead to better memory utilization
because each subproblem can be solved in place or in a smaller memory space.
This is particularly true in algorithms like Quick Sort.
6. Versatility:
o The divide and conquer strategy is versatile and can be applied to a wide range
of problems, including sorting, searching, matrix multiplication, and
computational geometry.

Disadvantages of Divide and Conquer

1. Overhead of Recursion:
o The divide and conquer approach typically involves recursive function calls,
which can introduce overhead due to the cost of maintaining the call stack.
This overhead can be significant for problems with many small subproblems.
2. Redundant Computations:
o In some cases, especially in naive implementations, divide and conquer can
result in redundant computations. For example, in the basic version of
recursive Fibonacci calculation, many subproblems are solved multiple times.
This can be mitigated by using techniques like memoization or dynamic
programming.
3. Increased Space Complexity:
o Some divide and conquer algorithms, like Merge Sort, require additional space
to combine the results of subproblems. This can lead to increased space
complexity, which might be a limitation in memory-constrained environments.
4. Non-Trivial Implementation:
o Implementing divide and conquer algorithms can be more complex than
straightforward iterative algorithms. It requires careful design to ensure that
the subproblems are handled correctly and efficiently, and that the results are
combined properly.
5. Not Always Optimal:
o Divide and conquer is not always the best approach. For some problems, other
strategies like dynamic programming, greedy algorithms, or even brute-force
methods might be more efficient or easier to implement.
6. Difficulty in Identifying Subproblems:
o For some problems, it may not be obvious how to divide the problem into
subproblems, or the subproblems may not be independent, which can
complicate the application of divide and conquer.
Design and Analysis of Algorithms (4CSGC2051)
Design and Analysis of Algorithms (4CSGC2051)
Design and Analysis of Algorithms (4CSGC2051)

Summary

Divide and conquer is a powerful strategy with significant advantages, especially in terms of
simplifying complex problems and enabling parallelism. However, it also has its downsides,
such as the potential for increased overhead, redundant computations, and the complexity of
implementation. The effectiveness of divide and conquer depends on the nature of the
problem and the specific algorithm used.