DESIGN AND ANALYSIS OF
ALGORITHMS
Max Subarray Sum, Karatsuba
Debarati Dutta
Divide and Conquer Algorithms
Suitable for problems where
• Problem can be divided into sub problems similar to the original
problem
• The sub problems are smaller than the original problem
• Possible to recursively break the sub problem into further sub
problems of smaller size
• There is a base case for sub problems when sub problem is small
enough
Quick sort, Merge sort fall in this paradigm
Divide, Conquer and Combine
Divide and Conquer algorithms have three parts
• Divide the problem into a number of sub
problems that are smaller instances of same
problem
• Can create more than two subproblems ( 2 or
more sub problems)
• Binary search is NOT a DAC algorithm
• Conquer the sub problems by solving them
recursively. If they are small enough, solve the
subproblems as base cases
• Combine the solutions to the sub problems
into the solution for the original problem
Divide, Conquer and Combine…
Two more recursive steps …
Divide and Conquer Algorithm
DAC(a, i, j)
{
if(base_case(a, i, j))
O(1) if n is small
return( solution(a, i, j)) T(n) =
else f1(n) + 2T(n/2) + f2(n)
mid = divide(a, i, j) // f1(n)
b = DAC(a, i, mid) // T(n/2)
c = DAC(a, mid+1, j) // T(n/2) O (n logn)
d = combine(b, c) // f2(n)
return(d)
}
DAC Algorithms
Quick Sort Sorting algorithm. The algorithm picks a pivot element and partitions
the given array around the picked pivot, recursively
Merge Sort Sorting algorithm. The algorithm divides the array into two halves,
recursively sorts them and finally merges the two sorted halves
Closest pair of to find the closest pair of points in a set of points in the x-y plane
points
Maximum sub- In a one dimensional array that may contain both positive and negative
array sum integers, find the sum of contiguous subarray of numbers which has
the largest sum
Strassen’s Efficient algorithm to multiply two matrices
Karatsuba For fast multiplication of two n-digit numbers at most
Maximum Subarray Sum
• Maximum subarray sum - Contiguous array elements that provide
us the maximum sum given an array
-2 1 4 -5 -1 4 -1 5 8
2 1 0 5 6 14
-2 -5 6 -2 -3 1 5 -6 7
-4 5 7 -6 10 -15 3 16
Maximum Subarray Sum – Naïve Method
int findMaxSubarraySum(int Array[], int n)
{
int maxSubarraySum = INT_MIN;
for(int i=0; i<n; i=i+1)
{ Total count of nested loop iterations
int subarraysum = 0; = N + (N-1) + (N-2)….+ 2+ 1
for(int j=i; j<n; j=j+1) = (N )(N+1)/2
{
subarraysum += Array[j]; O(n2)
if (subarraysum > maxSubarraySum)
maxSubarraySum = subarraysum;
}
}
return maxSubarraySum;
}
MaxSubarraySum – Divide and Conquer
Method
• Divide and Conquer – Divide the array into two Halves
0 1 2 3 4 5 6 7
-2 -5 6 -2 -3 1 5 -6
Three things might happen.
▪ Max Subarray Sum is in left Half (Make a recursive call) -> L
▪ Max Subarray Sum is in Right Half (Make a recursive call) -> R
▪ Max Subarray Sum such that Subarray crosses the mid point -> C
▪ MaxSubarraySum = Max of L, R and C
Max Subarray Sum such that Subarray crosses
the mid point
L 6 0 1 2 3 4 5 6 7
R 6 -2 -5 6 -2 -3 1 5 -6
C ?
-1 +4 -2 Σ -3 -2 +3 -3
L 6
R 6
+7
C 7
-2 -5 6 -2 -3 1 5 -6
MaxSubarraySum = 7
Max Subarray Sum - Example
0 1 2 3 4 5 6 7
-2 -5 6 -2 -3 1 5 -6
0 1 2 3 0 1 2 3
-2 -5 6 -2 -3 1 5 -6
-2 -5 6 -2 -3 1 5 -6
-2 -5 6 -2 -3 1 5 -6
L
Max Subarray Sum - Example R
C
0 1 2 3 4 5 6 7
6
-2 -5 6 -2 -3 1 5 -6 6
7
0 1 2 3 0 1 2 3
-2 1
-2 -5 6 -2 6 -3 1 5 -6 5
1 6
-2 6 -3 5
-2 -5 -5 6 -2 -2 -3 1 1 5 -6 -6
-7 4 -2 -1
-2 -5 6 -3 1 5 -6
-2
-2 -2 -5 -5 6 -2 -3 -3
1 1 5 5 -6 -6
6 -2
-2 -5 6 -3 1 5 -6
-2
Max Subarray Sum - Algorithm
MaxSubArray(A, p, r) T(n) = O(1) if n=1
T(n) = 2T(n/2) + O(n) if n>1
if (p == r) return A[p]
q = (p + r)/2
L = MaxSubArray(A, p, q-1) Using Master’s theorem
a=2, b=2, k=1, p=0
R = MaxSubArray(A, q+1, r)
a=bk p > -1 Case 2-a
C = MaxCrossingSubArray(A, p, q, r)
T(n) = θ(nlogba logp+1n)
return Max(L, R, C)
n log(n)
Example
• arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
[4, -1, 2, 1]
Karatsuba Faster Integer Multiplication
Algorithm
• Basic high school multiplication
(Naïve approach) is of order O(n2)
• n : number of digits 4 5 2 6
• For large numbers (n) …not X 3 4 7
efficient
• In Encrypted communication, 3 1 6 8 2
computer needs to perform + 1 8 1 0 4 0
multiplication with large numbers
(hundreds or even thousands) + 1 3 5 7 8 0 0
• Karatsuba algorithm helps us
perform the operation more 1 5 7 0 5 2 2
efficiently
• Efficient -Divide and Conquer
Method
Karatsuba Faster Integer Multiplication
Algorithm…
a b
x 1 4 6 1 2 3 146123 = 146000 + 123 = 146 * 103 + 123
y 3 5 2 1 2 0 352120 = 352000 + 120 = 352 * 103 + 120
c d
x = a * 10n/2 + b (a+b)(c+d) – ac – bd
= (ac + ad + bc - bd) – ac – bd
y = c * 10n/2 + d = (ad + bc)
x * y = (a * 10n/2 + b)(c * 10n/2 + d) n = max (size_base10(num1),
size_base10(num2))
= ac*(102m) + (ad + bc) * 10m + bd m = Ceiling(n/2)
= ac*(102m) + [(a+ b) (c + d) – ac – bd] * 10m + bd Split is m digits from the right
(ac) x102m + [(a+b)(c+d)-ac-bd] x 10m + bd
Karatsuba - Example
a b c d
Ϗ (146123, 352120)
n=6, m=3
bd
Ϗ (146, 352) Ϗ (123, 120) Ϗ (269, 472)
n=3, m=2 n=3, m=2 n=3, m=2
Ϗ (1, 3) Ϗ (46,52) Ϗ (47, 55) Ϗ (1, 1) Ϗ (23, 20) Ϗ (24, 21) Ϗ (2, 4) Ϗ (69,72) Ϗ (71, 76)
n=2, m=1 n=2, m=1 n=2, m=1 n=2, m=1 n=2, m=1 n=2, m=1
Ϗ (4, 5) Ϗ (6, 2) Ϗ (10, 7) Ϗ (2, 2) Ϗ (3, 0) Ϗ (5, 2) Ϗ (6,7) Ϗ (9,2) Ϗ (15,9)
Ϗ (4, 5) Ϗ (7, 5) Ϗ (11, 10) Ϗ (2, 2) Ϗ (4, 1) Ϗ (6, 3)
Ϗ (7,7) Ϗ (1,6) Ϗ (8,13)
(ac) x102m + [(a+b)(c+d)-ac-bd] x 10m + bd
Karatsuba - Example
a b c d 51452830760
Ϗ (146123, 352120)
n=6, m=3
51392 126968
bd
14760
Ϗ (146, 352) Ϗ (123, 120) Ϗ (269, 472)
n=3, m=2 n=3, m=2 n=3, m=2
3 2392 2585 1 460 504 4 4968 5396
Ϗ (1, 3) Ϗ (46,52) Ϗ (47, 55) Ϗ (1, 1) Ϗ (23, 20) Ϗ (24, 21) Ϗ (2, 4) Ϗ (69,72) Ϗ (71, 76)
n=2, m=1 n=2, m=1 n=2, m=1 n=2, m=1 n=2, m=1 n=2, m=1
20 12 70 4 0 10 42 18 135
Ϗ (4, 5) Ϗ (6, 2) Ϗ (10, 7) Ϗ (2, 2) Ϗ (3, 0) Ϗ (5, 2) Ϗ (6,7) Ϗ (9,2) Ϗ (15,9)
20 35 110 4 4 18
49 6 104
Ϗ (4, 5) Ϗ (7, 5) Ϗ (11, 10) Ϗ (2, 2) Ϗ (4, 1) Ϗ (6, 3)
Ϗ (7,7) Ϗ (1,6) Ϗ (8,13)
Karatsuba Algorithm
Step 3: Recursive Multiplications
Step 1: Determine Split Size (m)
Calculate n = max(digits in x, Instead of 4 multiplications (ac, ad, bc, bd), we do 3:
digits in y). [Link] ac (High parts product): z2 = Karatsuba(a, c)
Set m = ceil(n / 2). [Link] bd (Low parts product): z0 = Karatsuba(b, d)
Step 2: Split the Numbers [Link] Sum Product (The "Trick"): z1 =
Using integer arithmetic (where / Karatsuba(a + b, c + d)
is integer division and % is
Step 4: The Final Formula
modulus/remainder):
To find the middle term (ad + bc), we use the Gauss
•a = x / 10^m
trick:
•b = x % 10^m
Middle Term = z1 - z2 - z0
•c = y / 10^m
Combine everything to get the final result:
•d = y % 10^m
Result = (z2 * 10^(2m)) + ((z1 - z2 - z0) * 10^m) + z0
Karatsuba Algorithm – Time Comlexity
Step 1: Determine Split Size (m) Step 4: The Final Formula
Calculate n = max(digits in x, digits in y). To find the middle term (ad + bc), we use the Gauss
Set m = ceil(n / 2). trick:
Step 2: Split the Numbers Middle Term = z1 - z2 - z0
Using integer arithmetic (where / is integer division Combine everything to get the final result:
and % is modulus/remainder): Result = (z2 * 10^(2m)) + ((z1 - z2 - z0) * 10^m) + z0
•a = x / 10^m ϴ(n)
•b = x % 10^m
•c = y / 10^m
•d = y % 10^m
Step 3: Recursive Multiplications
Instead of 4 multiplications (ac, ad, bc, bd), we do 3:
[Link] ac (High parts product):
z2 = Karatsuba(a, c)
[Link] bd (Low parts product): T(n/2)
z0 = Karatsuba(b, d)
[Link] Sum Product (The "Trick"): T(n/2)
z1 = Karatsuba(a + b, c + d)
T(n/2)
Karatsuba Algorithm- Time Complexity…
T(n) = 3T(n/2) + O(n)
n: The size of the input (number of digits).
a = 3: The number of recursive calls (subproblems). We calculate ac, bd, and (a+b)(c+d).
b = 2: The factor by which the input size shrinks. We split the digits in half, so the new size is
n/2.
f(n) = O(n): The cost of the work done outside the recursion. This is the time taken to add
and subtract the results (the combining step), which is linear.
The Master Theorem handles recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n)
to n^(log_b a).
There are three cases:
[Link] 1: If log_b(a) > d (where d is the exponent of f(n)), then T(n) = O(n^log_b(a)).
[Link] 2: If log_b(a) = d, then T(n) = O(n^d * log n).
[Link] 3: If log_b(a) < d, then T(n) = O(f(n)).
Karatsuba Algorithm- Time Complexity…
Step A: Identify the values
•a = 3
•b = 2
•f(n) is O(n), so d = 1 (because n is the same as n^1).
Step B: Calculate the Critical Exponent (log_b a)
We need to calculate log_2(3) (log base 2 of 3).
Approx 1.585
Step C: Compare exponents
We compare the critical exponent (1.585) with the work exponent d (1).
•1.585 > 1
Because the critical exponent is larger, the cost of the recursive branching dominates
the cost of the linear addition work. This places us in Case 1.
T(n) = O(n^log_2(3)) or O(n^1.585)
Example
• x= 123456 and y=78901