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