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.