[martincmartin]

Um, O((s * (s + 1)) / 2) = O(m^2). Quadratic, not exponential.

[bnoordhuis]

Sorry, I updated my comment just as you posted yours.

But - and I don't want to sound pedantic - how is m^2 not exponential growth?

Edit: mea culpa guys, I carelessly translated from Dutch. You're all right: quadratic, not exponential growth.

[bigiain]

Because 2^m and m^2 are very different...

Using terminology like "exponential" and "quadratic" correctly in a discussion of algorithms is not pedantic...

[Locke1689]

Exponential growth is O(2^m). This is not pedantic -- it's definition. O(m^k) is polynomial, O(k^m) is exponential.

[cperciva]

how is m^2 not exponential growth

m^2 is exponential -- in the value 2. But the value 2 doesn't change very rapidly, so we tend to focus on the m component of the expression. :-)

[state_machine]

Because 2, the exponent in that expression, is a constant.

Exponential growth would be 2^m.

[theoretical]

x^2 is quadratic, 2^x (for example) is exponential.

Have a look at http://en.wikipedia.org/wiki/Time_complexity , it's pretty comprehensive.