Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size \(n_0\) gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than \(n_0\). Does that change the crossover point?
Both the algorithms were developed on my system in C++ (code can be downloaded from here). You can also find an embedded Python code that you can run directly from your browser at the bottom of the page.
The data collected is as follows (size is the number of elements processed and run times are in micro seconds):
Size
BruteForce
Recursive
20
1.1573
1.3096
21
1.1346
1.3642
22
1.2318
1.3632
23
1.3214
1.4604
24
1.4080
1.5070
25
1.4860
1.6002
26
1.6113
1.6982
27
1.7965
1.8065
28
1.8434
1.8172
29
2.1403
1.9220
30
2.0902
1.9593
31
2.2252
2.0011
32
2.3875
2.1071
So, on my computer \(n_0 = 28\).
However, it varies between 25 and 30 in different runs.
If we modify the the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than \(n_0\), the crossover point doesn’t change significantly.
However, in most cases, I have noticed there is not a single crossover point. Let’s say, recursive beats brute-force at \(n = 22\), but immediately after that (\(n = 23, 24\)) brute-force beats recursive, and then recursive beats brute-force again for \(n = 25\).
Python Code
import math
import time
import random
# Brute force method
def FindMaxSubarrayBruteForce(A, low, high):
left = low
right = high
sum = -math.inf
for i in range(low, high):
tempSum = 0
for j in range(i, high):
tempSum = tempSum + A[j]
if tempSum > sum:
sum = tempSum
left = i
right = j
return (left, right, sum)
# Method for finding crossing maximum sub-array
def FindMaxCrossingSubarray(A, low, mid, high):
left = low
right = high
leftSum = -math.inf
rightSum = -math.inf
sum = 0
for i in reversed(range(low, mid)):
sum += A[i]
if sum > leftSum:
leftSum = sum
left = i
sum = 0
for j in range(mid, high):
sum += A[j]
if sum > rightSum:
rightSum = sum
right = j
return (left, right, leftSum + rightSum)
# Recursive method
def FindMaxSubarrayRecursive(A, low, high):
if low + 1 == high:
return (low, low, A[low])
mid = (low + high) // 2
left = FindMaxSubarrayRecursive(A, low, mid)
right = FindMaxSubarrayRecursive(A, mid, high)
cross = FindMaxCrossingSubarray(A, low, mid, high)
if left[2] >= right[2] and left[2] >= cross[2]:
return left
elif right[2] >= left[2] and right[2] >= cross[2]:
return right
else:
return cross
# Number of iterations to run the algorithms to average out
# Note: If you run this on your computer, use higher values like 1000 or more
# For browser, it is kept lower so that it doesn't hang your browser
NUM_ITERATIONS = 10
# Test with some randomly created array with increasing input size
# We are explicitly starting from size 2, as for size 1, obviously recursive will be faster
# as it doesn't do anything and return the element directly
for input_size in range(2, 100):
arr = [random.randint(-100, 100) for _ in range(input_size)]
# Run brute force method and measure time
start = time.time()
for _ in range(NUM_ITERATIONS):
bf = FindMaxSubarrayBruteForce(arr, 0, len(arr))
bf_time = time.time() - start
# Run recursive method and measure time
start = time.time()
for _ in range(NUM_ITERATIONS):
rc = FindMaxSubarrayRecursive(arr, 0, len(arr))
rc_time = time.time() - start
if bf_time > rc_time:
print(f"Cross over point = {input_size}")
break