The Problem: "The input is a vector X of N real numbers; the output is the maximum sum found in any contiguous subvector of the input." A zero length subvector has maximum 0.0.

[From Programming Pearls by Jon Bentley.]

In the previous TidBits we came up with solutions that had executions times that were Order N**3, N**2, N*Log(N) and N respectively.

Jon Bentley coded up these solutions and for the particular compiler and cpu he used he got respectively:

Run time msec	3.4 * N**3	13 * N**2	46 * N * Log(N)	33 * N
N = 10**2	3.4 sec	.13 sec	0.03 sec	0.003 sec
N = 10**3	0.94 hr	13 sec	.45 sec	0.033 sec
N = 10**4	39 days	22 min	6.1 sec	0.33 sec
N = 10**5	108 yrs	1.5 days	1.3 min	3.3 sec
N = 10**6	108,000 yrs	5 months	15 min	33 sec
Max N in 1 sec	67	280	2000	30,000
Max N in 1 min	260	2,200	82,000	2,000,000
Max N in 1 hr	1000	17,000	3,500,000	120,000,000
Max N in 1 day	3,000	81,000	73,000,000	2,800,000,000

So, worrying about the Order of an algoritm may be in order.