Quadratic time to sort in a simple case?
Ivan Kazmenko
gassa at mail.ru
Fri Apr 19 15:12:44 PDT 2013
>> With n = 30_000 as in the example, this takes time of the
>> order of a
>> second on a modern computer, which is clearly O(n^2). I am
>> using DMD
>> 2.062.
>
> Optimization flags if any?
Both "-O" and no-flags give quadratic behavior.
Well, if that does not convince you the time grows faster than
n-log-n, maybe this comparison shall (dmd -O, Core i7-2600K @3400
MHz):
n T, seconds
15_000 0.312
30_000 1.076
60_000 3.775
120_000 11.247
With n growing x2, the time grows x3 to x4 at each step.
More information about the Digitalmars-d-learn
mailing list