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?
I have included python code that I used to implement both versions of this algorithm and compare their running times. I found \(n_0\) to be roughly \(70\), but it varied quite a bit. When I made a change to the base case to invoke brute-force when the array size was less than \(70\), it change the crossover point quite a bit in that recursive no longer beat brute-force even for very high values of \(n\). However when I made the change to the base case to use brute force for problem sizes that were greater than \(70\) the result was brute-force and recursive being very close in runtime such that it almost seemed random which would win out on the other one.
import math
import random
import time
def build_array(length):
A = []
for i in range(0, length):
A.append(random.randint(-10000, 10000))
return A
def brute_force_find(A):
sum = -float("inf")
left = 0
right = 0
for i in range(len(A)):
temp_sum = 0
for j in range (i, len(A)):
temp_sum += A[j]
if temp_sum > sum:
sum = temp_sum
left = i
right = j
return [left, right, sum]
def find_max_crossing_subarray(A, low, mid, high):
left_sum = -float("inf")
sum = 0
max_left = -float("inf")
for i in reversed(range(low, mid+1)):
sum = sum + A[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = -float("inf")
sum = 0
max_right = -float("inf")
for j in range(mid + 1, high + 1):
sum = sum + A[j]
if sum > right_sum:
right_sum = sum
max_right = j
return [max_left, max_right, left_sum + right_sum]
def recursive_find(A, low, high):
if low == high:
return [low, high, A[low]]
else:
mid = math.floor((low + high)/2)
[left_low, left_high, left_sum] = recursive_find(A, low, mid)
[right_low, right_high, right_sum] = recursive_find(A, mid + 1, high)
[cross_low, cross_high, cross_sum] = find_max_crossing_subarray(A, low, mid, high)
if left_sum >= right_sum and left_sum >= cross_sum:
return [left_low, left_high, left_sum]
elif right_sum >= left_sum and right_sum >= cross_sum:
return [right_low, right_high, right_sum]
else:
return [cross_low, cross_high, cross_sum]
def timed_brute_force_find(A):
start = time.perf_counter()
calculation = brute_force_find(A)
elapsed_time = time.perf_counter() - start
return calculation, elapsed_time
def timed_recursive(A):
start = time.perf_counter()
calculation = recursive_find(A, 0, len(A)-1)
elapsed_time = time.perf_counter() - start
return calculation, elapsed_time
for i in range (1, 20000):
A = build_array(i)
brute = timed_brute_force_find(A)
recursive = timed_recursive(A)
if brute[0] != recursive[0]:
print("Error, different results")
exit(1)
if brute[1] > recursive[1]:
dif = brute[1] - recursive[1]
print("n=" + str(i) + ". Recursive was " + str(dif) + " faster.")
else:
dif = recursive[1] - brute[1]
print("n=" + str(i) + ". Brute-Force was " + str(dif) + " faster.")