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