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?

Here is the data collected in my computer (size is the number of elements processed and times are in seconds):

Size Brute Force Recursive
2 0.050000 0.090000
3 0.080000 0.180000
4 0.120000 0.180000
5 0.080000 0.170000
6 0.110000 0.220000
7 0.150000 0.270000
8 0.210000 0.310000
9 0.260000 0.370000
10 0.320000 0.420000
11 0.370000 0.490000
12 0.450000 0.550000
13 0.540000 0.600000
14 0.570000 0.660000
15 0.660000 0.700000
16 0.740000 0.750000
17 0.810000 0.800000

So, the value of $n_0$ is 17 in my computer. However, it varies a bit. I have noticed it is mostly 17 but sometimes takes any value between 17 and 25.

If we modify the the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than 17, the crossover point doesn’t change significantly.

Here is the code written in c to get these results.