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